如何在dijkstra算法中保存最短路径 [英] how to save shortest path in dijkstra algorithm

问题描述

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

So first let's define Dijkstra algorithm:
Dijkstra's algorithm finds single-source shortest paths in a directed graph with non-negative edge weights.
I want to know how can I save the shortest path form s to t with Dijkstra algorithm.
I searched on google, but I couldn't find anything particular; I also changed Dijkstra algorithm, but I could't get any answer. How can I save the shortest path from s to t with Dijkstra?
I know my question is basic and unprofessional, but any help would be appreciated. Thanks for considering my question.

推荐答案

如果你看一下 pseudocode 来自您提供的维基百科链接，您将在其中看到一个名为 prev[] 的数组.对于图中的每个节点v，该数组包含源节点s<之间最短路径中的前一个节点u/strong> 和 v.(此数组也称为前驱或父数组.)

If you look at the pseudocode from the Wikipedia link you gave, you'll see an array in there called prev[]. This array contains, for each node v in the graph, the previous node u in the shortest path between the source node s and v. (This array is also called the predecessor or parent array.)

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

In other words, the shortest path between s and v is:

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

从s到u的路径可能中间有几个节点，所以要重建从s到v<的路径/strong>，您只需使用主伪代码下方的代码片段(target 是 v>):

The path from s to u might have several nodes in between, so to reconstruct the path from s to v, you just walk back along the path defined by the prev[] array using the code snippet below the main pseudocode (target is 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

这篇关于如何在dijkstra算法中保存最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！