最有效的最短路徑算法非負邊緣圖

-1

什麼是圖形進行最有效的最短路徑算法，不針對，只提供了這五個算法正面的邊緣？最有效的最短路徑算法非負邊緣圖

所以我知道Dijkstra的不能負邊緣被使用，且運行時間的O（E * logV）其中，E是邊和V的數量是頂點的數目，所以這將是我最好的猜測。它是否正確？

2015-10-16 martin

'DAG'是不是一個真正的算法（它是一類圖），其餘也不同他們做了什麼：Dijkstra算法（在其原來的形式）的單一來源單一目標，貝爾曼 - 福特是單一來源所有頂點和Floyd-Warshall爲您提供任意兩個頂點之間的最短路徑。 – biziclop

如果你能提供一個很好的啓發式方法，'A *'可能是最有效的。 – piotrekg2

@ piotrekg2 ......這是Dijkstra算法的知情版本。 – biziclop

如果你需要找到一個加權圖的最短路徑，BFS將是最好的選擇，但是如果有在邊緣上的權重，而你只需要找到一個單一來源之間的最佳路線和一個或許多其他節點，迪傑斯特拉將是最好的選擇。如果你需要找到兩個對節點之間的最短路徑（即具有多個來源），最好的選擇是弗洛伊德，沃肖爾。

2015-10-16 10:58:23

回答