如何使用Dijkstra获得节点到节点的最短路径?(带有邻接列表并指定开始节点和结束节点)

Question

我一直在使用Dijkstra进行一个项目。

我想用我自己的图来测试Dijkstra，在这种情况下，我使用的是我从Geeksformeeks获得的实现：

https://www.geeksforgeeks.org/dijkstras-algorithm-for-adjacency-list-representation-greedy-algo-8/

输出

Vertex   Distance from Source
0          0
1          4
2          12
3          19
4          21
5          11
6          9
7          8
8          14

在这种情况下，这个实现给了我距离的值，但我想获得节点到节点的最短路径，并指定开始节点和结束节点。

Answer 1

我建议的一个简单方法是保留一个额外的数据结构来存储2个顶点之间关系的父级。因此，基本上，每当你更新未确定顶点v的暂定距离(u，v(时(ps：它表示迭代中的当前顶点是u(，你就会存储/更新这个关系，即源可能通过u到达v。如果你后来发现到v的较短距离(w，v(，你就必须更新这个关系。因此，在确定目标顶点后，可以使用此数据结构来检索完整的节点到节点的最短路径。