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

迪杰斯特拉算法為什么不能有負(fù)權(quán)邊？

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

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

元素的最短路徑：

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

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

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

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

具體的程序可以在線查看

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

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

0，3，4

3，0，-2

4，-2，0

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