Нахождение ВСЕХ кратчайших путей между двумя узлами в графе, имеющем многомерный массив предшественников

Question

, поэтому я пытался найти способы найти ВСЕ кратчайшие пути между двумя конкретными узлами в невзвешенном графе, и я написал код до того момента, когда я создал массив «предшественник», который отслеживаеткакие узлы я использовал для достижения данного узла.Этот массив является многомерным массивом, поэтому, например, если кратчайший путь от A до D может быть от A> B> D ИЛИ A> C> D, тогда массив предшественника будет выглядеть следующим образом (где первая строка является индексом, итогда строки ниже являются многомерным массивом):

A    | B    | C    | D    | 
---------------------------
     | A    | A    | B    |
---------------------------
     |      |      | C    |

Но теперь я заблудился о том, как найти каждую перестановку в этом массиве предшественника, чтобы получить все возможные комбинации кратчайших путей, которые затем можно распечатать, например, Iхотел бы распечатать:

All shortest paths:
A > B > D
A > C > D

Я слышал, как люди говорят, что вы можете сделать это с помощью рекурсии?Но я очень потерян.(Также обратите внимание, что меня не слишком беспокоит сложность времени).Спасибо за любые рекомендации!

Answer 1

Я слышал, как люди говорят, что вы можете сделать это с помощью рекурсии?

Я не уверен, что они имеют в виду, когда говорят это, но я даю вам простой способ решить эту проблему, и это также поможет решить эту проблему вовремя.Решите эту ситуацию, используя BFS.ИМО, это ваша лучшая ставка.

Решение :

Example graph:
(A,B,C,D,E)
A->B, A->C, B->D, B->E, C->E, D->E

Source: A, Destination: E
Paths: (marked with # are solution paths)
# A->B->E
# A->C->E
  A->B->D->E

1. Начните с исходного узла.Сохраняйте очередь, каждый элемент имеет 3 информационных пункта:
   • Узел
   • Уровень
   • Путь (до сих пор)
2. DoBFS на графике.На каждом уровне проверьте, достигнут ли пункт назначения.Продолжайте до тех пор, пока это не будет сделано.
3. Когда вы достигнете цели на определенном уровне, не останавливайтесь на достигнутом, как в обычных случаях.Вам нужно полностью пройти этот уровень и остановиться, когда вы закончите с этим уровнем.
4. Напечатайте все пути для пункта назначения, это будет ваш ответ.

Работа над этимнаш пример:

• Каждый элемент очереди представлен как кортеж из 3 значений (Узел, Уровень, Путь)

Начальная очередь: (A, 0,null)

Level         Queue
 0            (A,0,null)
 1            (B,1,A)
 1            (C,1,A)
 2            (D,2,AB)
 2            (E,2,AB)      #       --> found destination, so, complete L2 fully
 2            (E,2,AC)      #
 3...stop

Печать путей: ABE и ACE сверху.