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

Question

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

Answer 1

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

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