迪杰斯特拉算法為什么不能有負(fù)權(quán)邊？如果你錯(cuò)了，Dijkstra算法的單源最短路徑不能有負(fù)邊權(quán)，因?yàn)樗菑漠?dāng)前的最小路徑長度逐漸增加，不再返回操作。如果邊權(quán)為負(fù)，自然采用Bellman算法，另一種方法是

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

如果你錯(cuò)了，Dijkstra算法的單源最短路徑不能有負(fù)邊權(quán)，因?yàn)樗菑漠?dāng)前的最小路徑長度逐漸增加，不再返回操作。如果邊權(quán)為負(fù)，自然采用Bellman算法，另一種方法是Floyd算法。這兩種算法都是在沒有負(fù)權(quán)環(huán)的情況下使用的，因?yàn)橐粋€(gè)圓的旋轉(zhuǎn)越來越小，旋轉(zhuǎn)越來越小Kruskal算法是尋找最小生成樹，而且沒有負(fù)邊權(quán)的問題

最常用的最短路徑算法是Dijkstra。使用條件是你能寫。在稀疏圖中，非負(fù)權(quán)邊SPFA算法是最常用的最短路徑算法，不存在負(fù)環(huán)。而且，你應(yīng)該寫Floyd是常用的算法來尋找多源最短路徑。對(duì)于程序apes，Dijkstra是最常用的OIer算法，如果它不是稠密圖，就必須編寫SPFA，因?yàn)镾PFA在稀疏圖上太快了

取負(fù)距離是最短路徑問題。負(fù)權(quán)最短路徑不適合Dijkstra算法。然而，基于松弛技術(shù)的BellmanFord和Floyd算法是適用的。采用Floyd算法計(jì)算多點(diǎn)間的最短路徑。具體來說，n-2輪松弛法用于計(jì)算多個(gè)點(diǎn)之間的最短路徑，即對(duì)任意兩點(diǎn)窮盡第三點(diǎn)，并嘗試用通過第三點(diǎn)的距離來代替距離。完成后，再進(jìn)行一輪放松。如果距離繼續(xù)減小，則存在負(fù)加權(quán)有向環(huán)，并且最短路徑不存在（可以保持在附近），否則當(dāng)前路徑就是最短路徑。然而，本課題的主要意義在于圖形具有特殊性。它的方向邊緣只能由小到大。這更簡單。以某個(gè)點(diǎn)結(jié)束的路徑只能由小于該點(diǎn)的頂點(diǎn)和它們之間的邊來確定。這是一個(gè)動(dòng)態(tài)規(guī)劃問題。它可以表示為：其中d[k]是在頂點(diǎn)k處結(jié)束的最長路徑的長度，d（J，k）表示J和k之間具有定向邊的距離。如果圖由一個(gè)特殊的鄰接表（逆鄰接表，邊按端點(diǎn)組織）表示，這是一個(gè)O（E）復(fù)雜度算法，最終的答案是d[k]的最大值。

對(duì)于網(wǎng)絡(luò)中有負(fù)權(quán)弧時(shí)，可以使用哪種算法求取最短路？

Dijkstra是貪婪的，一次找到一個(gè)離震源點(diǎn)（Dmin）最近的點(diǎn)，然后將距離設(shè)置為從該點(diǎn)到震源點(diǎn)（d[i]<--Dmin）的最短路徑；但是，如果存在負(fù)權(quán)重邊，有可能首先傳遞不最接近源點(diǎn)的次優(yōu)勢（dmin”），然后通過負(fù)權(quán)重側(cè)l（l<0）使路徑之和變?。╠min），這樣Dijkstra就會(huì)丟失。

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

0，3，4

3，0，-2

4，-2，0

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