没有“previous”向量的Dijkstra算法

Question

我对查找图中任何节点和根/源之间的最小距离感兴趣。所有链接都有重量。我不认为我需要使用previous[]，如the Wikipedia article所示，因为我不需要知道每个节点的父节点。那是对的吗？另外，如果权重都等于一，我想我可以运行一个BFS？

Answer 1

完全可以实现无后向指针的Dijkstra算法;我知道这是因为I've done it myself。 :-)结果是，一旦你完成了，你将无法恢复最短路径，但是如果你需要的只是路径长度，那应该是非常好的。

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