當所有邊具有相同權重時，Dijkstra算法

如果給定圖中所有邊具有相同權重，Dijkstra算法是否仍然會找到2個頂點之間的最短路徑？謝謝！當所有邊具有相同權重時，Dijkstra算法

2014-01-24 sinou

是Dijkstra算法的neightbour節點之一甚至可以找到最短路徑當所有邊緣具有相同的重量時。 dijkstra的時間複雜度爲O（（V + E）logV）。因爲BFS的時間複雜度爲O（V + E），所以BFS算法比dijkstra漸近地快。

2014-02-04 10:10:43 tanmoy

是的，但你可能想看看Breadth-first search，這解決了你所指的情況。要查找路徑，你可以做一個遞歸函數啓動與標記的距離n命運的節點，並移動到與標記的距離N-1

2014-01-27 13:00:27 germangb

回答