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

  • Z时代
  • 2024-01-10
  • 分类：问答

因此，首先让我们定义Dijkstra算法：

Dijkstra的算法在具有非负边权重的有向图中找到单源最短路径。

我想知道如何使用 算法将最短路径形式s保存到t 。

我在Google上进行了搜索，但找不到任何特别的内容；我也更改了Dijkstra算法，但无法得到任何答案。如何使用

保存从s到t的最短路径？

我知道我的问题是基本的和不专业的，但是任何帮助将不胜感激。感谢您考虑我的问题。

回答：

如果您从给出的Wikipedia链接中查看伪代码，则会在其中看到一个名为的数组prev[]。对于图中的每个节点

与 之间最短路径中的 节点 。（此数组也称为 数组或

数组。） ***

换句话说， 和 之间 最短路径是：

s -> u -> v
where u = prev[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

以上是 如何在dijkstra算法中保存最短路径 的全部内容， 来源链接： utcz.com/qa/426857.html

回到顶部