由网友(别把装逼当典范)分享简介：因此​​，首先让我们来定义的Dijkstra算法：Dijkstra算法发现在一个有向图具有非负边权单源最短路径。我想知道我怎么能保存的最短路径形式S到T是 Dijkstra算法算法。我搜索谷歌，但我无法找到一些特别的东西，我改变Dijkstra算法，但我便无法得到答案，所以我们可以节省最短路径形式S到T是 Dij...

因此​​，首先让我们来定义的Dijkstra算法： Dijkstra算法发现在一个有向图具有非负边权单源最短路径。 我想知道我怎么能保存的最短路径形式S到T是 Dijkstra算法算法。 我搜索谷歌，但我无法找到一些特别的东西，我改变Dijkstra算法，但我便无法得到答案，所以我们可以节省最短路径形式S到T是 Dijkstra算法？ 我知道我的问题是基本的和不专业，但任何帮助，将不胜感激，谢谢您考虑我的问题

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 search on google but I couldn't find some thing particular and I change dijkstra algorithm but I could't get answer so can we save shortest path form s to t with dijkstra? I know my question is basic and unprofessional but any help would be grateful thanks for considering my question

推荐答案

如果你看的从你给了维基百科的链接伪code ，你会看到有一个数组名为 preV [] 。该芯片包括，对每个节点的 v 在图中，在 previous 节点的 U 在源节点之间的最短路径取值和 v 。 （此阵也被称为 predecessor ​​或父阵列。）

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.)

在换句话说，之间的最短路径的取值和 v 是：

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

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

这是该路径的取值为 U 可能有几个节点之间，所以要重建，从取值的路径为 v ，您只需步行回顺使用下面的主伪code中的code段由 preV [] 数组定义的路径（ 目标是 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