如何在dijkstra算法中保存最短路径
首先让我们定义Dijkstra算法：
Dijkstra算法在具有非负边权重的有向图中找到单源最短路径。
我想知道如何使用Dijkstra算法将最短路径形式保存到t中。
我在谷歌搜索，但我找不到任何特别的; 我也改变了Dijkstra算法，但我无法得到任何答案。 如何用Dijkstra保存从s到t的最短路径？
我知道我的问题是基本的和不专业的，但任何帮助将不胜感激。 感谢您考虑我的问题。
如果你从维基百科链接中看到伪代码，你会看到一个名为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
大多数使用此算法的库可能会为您提供一种方法来执行此操作。 但通常只需跟踪每个节点的路径。 即给每个节点的attrribute shortestPathToNode在其中存储节点列表
一个非常简短的方法是使用递归和“父数组”。 如果将所有点的父项初始化为-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;
}
请注意，不是打印出“j”，而是将其存储在全局向量（或其他非C语言的数据类型）中以备后用。
链接地址: http://www.djcxy.com/p/35185.html