Может я чего не понял, но если ноды схлопываются только в том случае, когда между ними единственный маршрут, то для каждой пары нод нужно искать путь из одной ноды в другую.

Сложность "тупого рекурсивного" поиска маршрута прикидочно может достигать 50 000 (кол-во нод) x 5 (путей из каждой ноды) => до 50 - 250 тысяч рекурсий/циклов, и отжирать примерно столько же стека. Теоретически возможно тут нужно было бы 50 000 возводить в степень 5-ки, но это если искать все маршруты. Нам же нужен только факт, что такой маршрут есть, т.е. если мы повторно входим в ноду, то поиск сразу же прекрашаем.

Результат работы массив из 5 ячеек, есть ли (сколько) маршрутов в соседние ячейки. Плюс временный массив на 50 000 элементов, где хранится были ли мы уже в этой ноде.

Таких поисков нужно запускать 50 000 раз.

Поскольку схлопывание может быть рекурсивным (например граф вырождается в банальное кольцо), алгоритм возможно рекурсивно запускать до 50 000 раз.

Время работы одного прогона на Java (при оптимизации), я бы оценил от 10 000 секунд, т.е. где-то 3-10 часов (железо уровня AWS tiny instance) для одного прогона. Но это без рекурсивного схлопывания. При многопроцессорности кратно меньше.

Для рекурсивном схлопывание, наверное, нужно посчитать один раз матрицу N x N ( 50 x 50 = 2 500 000 000 элементов) кол-во маршрутов из A в B. Т.к. при схлопывание кол-во марщрутов из A и B изменится не должно (мне так кажется), то не нужно будет перевычислять маршруты.

Кол-во маршрутов из A в B нам интересно только 0 - нет маршрута, 1 - толкьо один маршрут, 2 - два и _более_ маршрута (схлопывать нельзя).

Крайне не оптимально. Я бы вершины кодировал бы просто целым числом в массиве (т.е. до 2 млр. вершин), сответственно outgoingEdges, incomingEdges можно сделать просто

int[] outgoingVertex;

Аналогично и хранение результатов в стеке, все возвраты - тупо int. Объекты даром не нужны. Коллекции - только оптимизированные (не стандартные!) для работы с примитивными типами.