迪杰斯特拉算法為什么不能有負權邊？你錯了嗎？單源最短路徑Dijkstra算法從當前的最小路徑長度開始，逐漸增加，不再返回，因此不能有負的邊權。如果它有負的邊權，它自然使用Bellman算法另一種替代方

迪杰斯特拉算法為什么不能有負權邊？

你錯了嗎？單源最短路徑Dijkstra算法從當前的最小路徑長度開始，逐漸增加，不再返回，因此不能有負的邊權。如果它有負的邊權，它自然使用Bellman算法另一種替代方法是Floyd算法。后兩種算法的前提是不存在負權環(huán)。因為Kruskal算法是尋找最小生成樹，邊權為負時沒有問題

現(xiàn)在最常用的最短路徑算法是Dijkstra。它的使用條件是你可以寫，并且在圖中沒有負權邊。SPFA是目前稀疏圖中最常用的最短路徑算法，并且沒有負循環(huán)，需要能夠編寫Floyd。它是從多個源中尋找最短路徑最常用的算法。對于程序ape，Dijkstra對于OIer來說是非常簡單的，只要它不是稠密圖，就一定要寫SPFA，因為SPFA在稀疏圖上太快了

元素的最短路徑：

1。如果稀疏圖沒有負權環(huán)，我們可以使用SPFA，時間復雜度O（km）

m是邊數(shù)，K是平均隊列數(shù)

2。如果稠密圖沒有負權環(huán)，我們推薦Dijkstra如果有負權環(huán)，可以試試Floyd，O（n^3）

任意兩點的最短路徑：Floyd最好實現(xiàn)，基于Johnson（high efficiency of sparse graph）的重新標記也很好

具體的程序可以在線查看

由于Dijkstra貪心，他總是找到一個最接近源點（Dmin）的點，然后將距離確定為從該點到源點的最短路徑（d[i]<--Dmin）；但是如果有一個負權重邊，可以先傳遞一個離源點不最近的子優(yōu)勢（Dmin”），然后傳遞負權重邊L（L<0）使路徑之和變?。―min”），這樣Dijkstra就會丟失。

例如，n=3，鄰接矩陣：

0，3，4

3，0，-2

4，-2，0

使用Dijkstra得到d[1，2]=3，實際上，d[1，2]=2，這使得路徑通過1-3-2遞減。