沒有「previous」向量的Dijkstra算法

Question

我對查找圖中任何節點和根/源之間的最小距離感興趣。所有鏈接都有重量。我不認爲我需要使用previous[]，如the Wikipedia article所示，因爲我不需要知道每個節點的父節點。那是對的嗎？另外，如果權重都等於一，我想我可以運行一個BFS？

Answer 1

完全可以實現無後向指針的Dijkstra算法;我知道這是因爲I've done it myself。 :-)結果是，一旦你完成了，你將無法恢復最短路徑，但是如果你需要的只是路徑長度，那應該是非常好的。

至於你的第二個問題，是的，你可以直接用單位重量的BFS。 Dijkstra算法按照在BFS中遇到的順序訪問節點，如果所有邊具有相同的正成本。