c++ - 没有“先前”向量的 Dijkstra 算法

Question

我有兴趣找到图中任何节点与根/源之间的最小距离。所有链接都有权重。我不认为我需要使用previous[]，在维基百科文章中指出，因为我不需要知道每个节点的父节点。那是对的吗？此外，如果权重都等于 1，我想我可以运行 BFS？

Answer 1

完全可以在没有反向指针的情况下实现 Dijkstra 算法；我知道这一点，因为我自己做过。:-) 结果是，一旦完成，您将无法恢复最短路径，但如果您需要的只是应该完全没问题的路径长度。

至于你的第二个问题，是的，你可以直接使用带有单位权重的 BFS。如果所有边都具有相同的正成本，Dijkstra 的算法会按照它们在 BFS 中遇到的顺序访问节点。