显示两个节点之间最短路径的节点

Question

假设我们使用 Dijkstra 算法，现在我们知道源节点与图中每个节点之间的最短距离。我应该怎么做才能知道每个距离访问了哪些节点？

Answer 1

每当您找到到某个节点的较短路径并因此减少其距离时，您还应该记录该节点的前任节点。当您发现新距离时，这就是您正在枚举的边缘列表的节点。

完成后，您可以从任何节点通过前驱链回溯，以找到到该节点的最短路径上的所有节点。