查找具有多维前置数组的图形中两个节点之间的所有最短路径

Question

所以我一直在尝试寻找在未加权图中查找两个特定节点之间所有最短路径的方法，并且我已经编写了代码，直到我建立了一个"前身"数组来跟踪我用来到达给定节点的节点。此数组是一个多维数组，因此，例如，如果从 A 到 D 的最短路径可以是从 A> B> D 或 A> C> D，那么前一个数组将如下所示(其中第一行是索引，然后下面的行是多维数组)：

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

但是现在我不知道如何找到这个前身数组中的每个排列，以获得可能出现的最短路径的每个可能组合，然后打印出来，例如我想打印出来：

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

我听人说你可以通过递归来做到这一点吗？但是我很迷茫。(另请注意，我不太担心时间复杂度)。感谢您的任何指导！

Answer 1

我听说有人说你可以通过递归来做到这一点？

我不确定他们在说这句话时的想法，但我给你一个简单的方法来解决这个问题，它也会在时间复杂的情况下解决这个问题。使用 BFS 解决此问题。IMO，这是你最好的选择。

解决方案：

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. 在图形上做一个BFS。在每个级别，检查是否到达目的地。继续此操作，直到完成。
3. 当您到达某个楼层的目的地时，不要像我们通常那样停在那里。您需要完全完成此级别，并在完成此级别后停止。
4. 打印目的地的所有路径，这将是您的答案。

在我们的示例中处理这个：

• 队列的每个元素都表示为 3 值元组(节点、级别、路径)

初始队列：(A，0，空)

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 从上方开始。