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

Question

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

Answer 1

一种非常简单的方法是使用递归和“父数组”如果将所有点的父数组初始化为-1，然后在完成dijkstra的后更新父数组，则可以从任何点递归返回，直到到达源并打印出路径。下面是一个非常简短且易于理解的递归片段：

// Function to print shortest path from source to j using parent array
void path(parent array, int j)
{
    // Base Case : If j is source
    if (jth element of parent is -1) return;
 
    path(parent, jth element of parent);
    print j;
}

请注意，您可以将其存储在全局向量（或其他与C无关的语言的数据类型）中，以供以后使用，而不是将j打印出来。

Answer 2

大多数使用此算法的库可能会为您提供一种方法。但一般来说，只需跟踪每个节点的路径即可。Ie为每个节点指定一个属性shortestPathToNode，在其中存储节点列表

Answer 3

如果您查看您提供的Wikipedia链接中的伪代码，您将看到一个名为prev[]的数组。对于图中的每个节点v，此数组包含源节点s和v之间最短路径中的前一个节点u。（此数组也称为前置或父数组。）

换句话说，s和v之间的最短路径为：

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

从s到u的路径之间可能有几个节点，因此要重建从s到v的路径，只需使用主伪代码（目标是v）下面的代码片段沿着prev[]数组定义的路径返回即可：

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