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