其實具體我有兩個問題。1.我知道最原始的地杰斯特拉算法復雜度是O(n^2)，但是用堆優化后，我們不再用一個數組去標記一個節點的最短路徑是否已經求出來，而是用隊列是否為空作為結束循環的依據。所以堆優化后的地杰斯特拉是否能夠用來求帶有負權邊的最短路徑？2.我覺得用堆之后的dij 其實 就跟spfa類似了，只是兩個的思想不同，一個是優先隊列，存放距離源點最近的點，而spfa只是一個簡單的隊列，縮小松弛的節點范圍。不知道這樣的理解是否正確？希望大家幫我解決一下，想了很久，網上也沒有具體的結論。
1 回答
千萬里不及你
TA貢獻1784條經驗 獲得超9個贊
你好，Dijkstra算法，帶有負權邊的情況下無論用不用優先隊列都是不可以的,你去畫個例子就可以看出來了。而spfa卻可以處理。
你也說了Dijkstra算法和spfa的思想不一樣，其實spfa，Dijkstra和BFS形式是有點類似。你不能說Dijkstra用了優先隊列就和spfa類似了，不用優先隊列就不類似了,因為用了優先隊列所以形式上有點相似。優先隊列只是優化了循環找最小值的方式。
此外spfa算法時間效率不穩定，如果圖十分復雜邊很多，spfa時間效率就很低了。Dijkstra堆優化時間復雜度很穩定。
添加回答
舉報
0/150
提交
取消