在具有多维前置数组的图中查找两个节点之间的所有最短路径
Finding ALL shortest paths between two nodes in a graph having a multidimensional predecessor array
所以我一直在尝试查找未加权图中两个特定节点之间的所有最短路径的方法，并且我已经编写了代码直到我建立了一个 "predecessor" 数组跟踪我用来到达给定节点的节点。这个数组是一个多维数组，例如，如果从 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
我听说有人说你可以通过递归来做到这一点？但是我很迷茫。 （另请注意，我不太担心时间复杂度）。感谢您的指导！
I have heard people say you can do this by recursion?
我不确定他们说这些的时候是什么意思，但是我给你一个简单的方法来解决这个问题，它也会在很好的时间复杂度下解决这个问题。使用 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
- 从源节点开始。保留一个队列，每个元素有 3 个信息点：
- 节点
- 等级
- 路径（到现在）
- 在图上做一个 BFS。在每个级别，检查是否到达目的地。继续这个直到完成。
- 当您到达某个级别的目的地时，请不要像我们通常那样停在那里。您需要完全完成此级别并在完成此级别后停止。
- 打印所有目的地路径，这就是您的答案。
在我们的示例中进行此操作：
- 队列的每个元素都表示为一个 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。
所以我一直在尝试查找未加权图中两个特定节点之间的所有最短路径的方法，并且我已经编写了代码直到我建立了一个 "predecessor" 数组跟踪我用来到达给定节点的节点。这个数组是一个多维数组，例如，如果从 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
我听说有人说你可以通过递归来做到这一点？但是我很迷茫。 （另请注意，我不太担心时间复杂度）。感谢您的指导！
I have heard people say you can do this by recursion?
我不确定他们说这些的时候是什么意思，但是我给你一个简单的方法来解决这个问题，它也会在很好的时间复杂度下解决这个问题。使用 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
- 从源节点开始。保留一个队列，每个元素有 3 个信息点：
- 节点
- 等级
- 路径（到现在）
- 在图上做一个 BFS。在每个级别，检查是否到达目的地。继续这个直到完成。
- 当您到达某个级别的目的地时，请不要像我们通常那样停在那里。您需要完全完成此级别并在完成此级别后停止。
- 打印所有目的地路径，这就是您的答案。
在我们的示例中进行此操作：
- 队列的每个元素都表示为一个 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。