algorithm - 使用最小优先级队列时如何跟踪 Dijkstra 算法中的最短路径？

Question

我正在尝试使用优先级队列实现 Dijkstra 算法。

根据我的理解，“Dijkstra 算法”允许找到最短的“路径”，因为它将返回一组形成最短路径的顶点 *。

从这里的这个答案https://stackoverflow.com/a/20217659/1663462 ，以及 ( Dijkstra's_algorithm#Algorithm ) 看来我应该能够使用两个数据结构来实现它:图形和队列数据结构。

---

但是，在我使用上述两个数据结构的实现中，当我最终到达目标节点时，我没有存储顶点路径？换句话说，我只有最短的距离(单个标量值)。

这意味着如何跟踪？我能想到的唯一方法是使用附加数据结构 - 一个数组或 HashMap ，其中 key 是顶点，value将是它的 parent 。

---

实际问题:

是否需要额外的数据结构来实现(“形成最短路径的顶点集 *”)？如果不是，我如何确定顶点？

Answer 1

您不必像您建议的那样跟踪每个顶点的整个路径。要自己生成 s-v 路径，您唯一需要为每个顶点 v 记录的是“发现”它的边。

换句话说，当算法发现顶点 v 时，您记录边 (u,v)，在该边上它获得了最小化的值与 s 的距离。

现在，假设图中的每个顶点 v 都有“发现”边，从 s 到 v 的路径可以是计算如下:如果 (u,v) 是为 v 存储的(“发现”)边，则从 s 到的最短路径v是从s到u的路径(可以递归计算)，后面是单边(u,v) 。

因此，要构造从 s 到 v 的最短路径，您从顶点 v 开始，然后沿着为 存储的边code>v 在相反的方向，并继续直到你到达 s。