我应该如何使用链表找到图中的最短路径
How should I find the shortest path in the graph using linked list
有n个节点，如果直接相连，则节点之间有边。
每条边没有权重和方向（如果节点a和b相连，则表示双向相连，而不是单向相连）。
根据图，我们可以画出邻接矩阵，它是一个二维数组，A[0][0]...A[n-1][n-1]。所以，问题是如何return最短路径。如果没有路径，应该return空路径。并且路径应该return使用链表。
|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 方法会很棒。
我相信 this 文章回答了您的问题。这个问题可以用Dijkstra算法解决。在您的情况下，每条边的权重等于 1，因此只需在伪代码中创建 dist_between(u,v) = 1 即可。解决方案的时间复杂度为 O(V^2)。注意，
previous[v]= 从起始节点到节点v的最短路径中第v个节点之前的节点。
也就是说，要想以最短的路径访问到第v个节点，就必须先到达previous [v]节点。所以使用这个 previous 数组，你可以 return 以任何你想要的方式得到最短路径。如果没有路径，伪代码中的dist[v]就会无穷大
有n个节点，如果直接相连，则节点之间有边。 每条边没有权重和方向（如果节点a和b相连，则表示双向相连，而不是单向相连）。
根据图，我们可以画出邻接矩阵，它是一个二维数组，A[0][0]...A[n-1][n-1]。所以，问题是如何return最短路径。如果没有路径，应该return空路径。并且路径应该return使用链表。
|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 方法会很棒。
我相信 this 文章回答了您的问题。这个问题可以用Dijkstra算法解决。在您的情况下，每条边的权重等于 1，因此只需在伪代码中创建 dist_between(u,v) = 1 即可。解决方案的时间复杂度为 O(V^2)。注意，
previous[v]= 从起始节点到节点v的最短路径中第v个节点之前的节点。
也就是说，要想以最短的路径访问到第v个节点，就必须先到达previous [v]节点。所以使用这个 previous 数组，你可以 return 以任何你想要的方式得到最短路径。如果没有路径，伪代码中的dist[v]就会无穷大