没有“前一个”的 Dijkstra 算法向量
我感兴趣的是找到图中任何节点与根/源之间的最小距离。所有链接都有权重。我认为我不需要使用 previous[]，如 维基百科文章，因为我不需要知道每个节点的父节点。这是正确的吗？另外，如果权重都等于 1，我想我可以运行 BFS 吗？
I am interested about finding the minimum distance between any node in a graph and the root/source. All links have weight. I don't think I need to use previous[], indicated in the Wikipedia article, since I don't need to know the parent of each node. Is that correct? Additionally, if the weights are all equal to one I guess I could just run a BFS?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
完全可以在没有后向指针的情况下实现 Dijkstra 算法；我知道这一点是因为我自己做过。 :-) 结果是，一旦完成，您将无法恢复最短路径，但如果您需要的只是路径长度，那应该完全没问题。
至于你的第二个问题，是的，你可以直接使用具有单位权重的 BFS。如果所有边都具有相同的正成本，Dijkstra 算法将按照 BFS 中遇到的顺序访问节点。
It is entirely possible to implement Dijkstra's algorithm without back pointers; I know this because I've done it myself. :-) The result is that you won't be able to recover the shortest paths once you're done, but if all you need are the path lengths that should be perfectly fine.
As for your second question, yes, you can just use a BFS in a direct with unit weights. Dijkstra's algorithm visits nodes in the order that they would be encountered in a BFS if all the edges have the same positive cost.