所以我一直在试图寻找方法来找到未加权图中两个特定节点之间的所有最短路径,并且我已经编写了代码,直到我建立了一个“前趋”数组来跟踪我的节点已经习惯了到达给定节点。这个数组是一个多维数组,所以例如,如果从A到D的最短路径可以来自A> B> D OR A> C> D,那么前一个数组将如下所示(其中第一行是索引,并且然后下面的行是一个多维数组):
A | B | C | D |
---------------------------
| A | A | B |
---------------------------
| | | C |
但现在我迷失了如何找到这个前任阵列中的每个排列,以获得可能的最短路径的每种可能组合然后打印出来,例如我想要打印出来:
All shortest paths:
A > B > D
A > C > D
我听说有人说你可以通过递归来做到这一点吗?但我很失落。 (另请注意,我并不太担心时间复杂度)。谢谢你的任何指导!
我听说有人说你可以通过递归来做到这一点吗?
我不确定他们在说这个时会想到什么,但是我给你一个简单的方法来解决这个问题,它也会在很好的时间内解决这个问题。使用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
在我们的例子上工作:
初始队列:(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。