algorithm - 我应该如何使用链表找到图中的最短路径

Question

有n个节点，如果直接相连，则节点之间有边。每条边没有权重和方向(如果节点a和b相连，则意味着双向相连，而不是单向相连)。

根据图，我们可以画出邻接矩阵，它是一个二维数组，A[0][0]...A[n-1][n-1]。所以，问题是如何返回最短路径。如果没有路径，应该返回空路径。路径应该使用链表返回。

 |A B C D E
A|0 1 0 1 0
B|1 0 1 0 0 
C|0 1 0 1 0
D|1 0 1 0 1
E|0 0 0 1 0

所以，根据上面的矩阵，从C到E的最短路径是[C,D,E]。从 A 到 C 的最短路径是 [A,B,C]。

我们应该使用时间复杂度为 O(n^2) 的伪代码。我简要地猜测 BFS 方法会很棒。

Answer 1

我相信this文章回答了你的问题。这个问题可以用Dijkstra算法解决。在您的情况下，每条边的权重等于 1，因此只需在伪代码中使 dist_between(u,v) = 1 即可。解决方案的时间复杂度为 O(V^2)。注意， previous[v]= 从起始节点到节点 v 的最短路径中第 v 个节点之前的节点。这意味着，为了以最短的路径访问第 v 个节点，您必须首先到达 previous [v] 节点。因此，使用这个 previous 数组，您可以按照您想要的任何方式返回最短路径。如果没有路径，伪代码中的dist[v]将为无穷大。