如何在dijkstra算法中保存最短路径

Question

首先让我们定义Dijkstra算法:
Dijkstra算法在具有非负边权重的有向图中找到单源最短路径.
我想知道如何使用Dijkstra算法将最短路径形式保存到t .
我搜索谷歌,但我找不到任何特别的东西; 我也改变了Dijkstra算法,但我无法得到任何答案.如何用Dijkstra保存从s到t的最短路径？
我知道我的问题是基本的和不专业的,但任何帮助都将不胜感激.谢谢你考虑我的问题.

Answer 1

如果你看一下你给出的维基百科链接中的伪代码,你会看到一个名为的数组prev[].对于图中的每个节点v,该数组包含源节点s和v之间的最短路径中的前一节点u.(此数组也称为前置或父数组.)

换句话说,s和v之间的最短路径是:

s -> u -> v
where u = prev[v]

从s到u的路径可能在它们之间有几个节点,因此要重建从s到v的路径,只需prev[]使用主伪代码下面的代码片段(目标为v)沿着数组定义的路径向后走:

1  S ? empty sequence
2  u ? target
3  while prev[u] is defined:                 // Construct the shortest path with a stack S
4      insert u at the beginning of S          // Push the vertex onto the stack
5      u ? prev[u]                             // Traverse from target to source
6  end while