Floyd-warshall、Bellman-ford、ASP、SPFA、dijkstra比較

dijkstra、SPFA、Bellman-ford、ASP、Floyd-warshall比較

類型	算法	限制	運作時間
單源最短路徑	dijkstra	不含負邊	依賴優先隊列實作，如O(E+VlgV)
SPFA	無限制（可檢測負圈）	O(k⋅∣E∣) (k≪∣V∣)O(k⋅∣E∣) (k≪∣V∣)
Bellman-Ford	無限制（可檢測并輸出負圈）	O(∣V∣⋅∣E∣)O(∣V∣⋅∣E∣)
ASP	無圈	O(∣V∣+∣E∣)O(∣V∣+∣E∣)
全源最短路徑	Floyd-Warshall	無限制	O(∣V∣^3)
備注：無向圖一條邊即可為一個圈

如果我們隻需要一個起點和一個終點，難道不應該比計算一個起點任意終點更節省時間麼？答案還真的不是，目前還沒有發現比算從源點到所有點更快的算法，是以一個起點一個終點也是用單源最短路徑。