負權重環演算法

① johnson演算法是什麼

Johson演算法是目前最高效的在無負環可帶負權重的網路中求所有點對最短路徑的演算法. Johson演算法是Bellman-Ford演算法, Reweighting(重賦權重)和Dijkstra演算法的大綜合. 對每個頂點運用Dijkstra演算法的時間開銷決定了Johnson演算法的時間開銷. 每次Dijkstra演算法(d堆PFS實現)的時間開銷是O( E * lgd(V) ). 其中E為邊數, V為頂點數, d為採用d路堆實現優先隊列ADT. 所以, 此種情況下Johnson演算法的時間復雜度是O( V * E * lgd(V) ).

② 為什麼Dijkstra演算法不能處理有負權值的圖

不能處理環這個要說么

③ 負載均衡權重輪詢演算法中的權重有什麼作用

不理解你說的權重是什麼，優先順序還是比率？
如果你有兩台伺服器，伺服器A和伺服器B
優先順序：伺服器A優先順序100，伺服器B優先順序50
流量全部分發到伺服器A上面，只有伺服器A掛掉才會分到B上面，類似於主備。
比率：伺服器A為3，服務B為1
如果一共有12個連接，伺服器A會分發到3+3+3 伺服器B會分發到1+1+1
也就是每4個連接中會有3個分發到伺服器A，剩下的1個分發到伺服器B。

④ bellman-ford演算法可以求出負權值的最短路徑嗎

可以，但是圖不能有負環

⑤ 求有向圖最短路徑演算法（權重可為負）

單元最短路徑：
1.如果沒有負權環的稀疏圖，可以用SPFA，時間復雜度O（KM）
M是邊數，K是平均入隊列的次數
2.如果沒有負權環的稠密圖，建議用Dijkstra O（N^2），用二叉堆可優化到
O（NlogN），斐波那契堆編程復雜度太高，不易於實現
3.如果有負權環，可以嘗試floyd,O(n^3)

任兩點最短路徑：floyd較好實現，基於重標號johnson也不錯（稀疏圖效率高）
具體程序可以上網查

⑥ 關於Dijkstra演算法

樓上正解，你找個圖自己用此演算法實踐一下就知道了，從A點出發，發現離A最近的點是B點，那麼我們就已經認為A到B的最短距離就是AB了，如果有負數，就指不定冒出個C點,AC+CB<AB;或者冒出個DE為很大的負值，AC+CD+DE+EF+FB<AB;等等諸如此類的情況。
簡單說來，你駕車從家出發到某地沿某條路只需經過一個收費站，但是遠在外省某地有個站不但不收你的費，你去了還會給你個千八百萬的歡迎光臨費，你能說你直接沿著這條路去某地是最省費用的？不計時間成本，繞到外省那個給你錢的地方，再繞回到你的目的地，還能賺錢呢。
而且一般權值為負的圖研究也比較少。有些帶負權的圖，某些點間還沒有最小距離呢。中間出個帶某條負權很大的邊的環圈，繞此一圈所經過的距離反而減少了，那就一直在此圈上繞啊繞啊繞到負的足夠大溢出為止。
當然考慮各種自己隨便假設出來的變種問題也是很有趣的。比如說邊帶有多個權值對應多次經過改變的消費，上面的問題有可能變成有解的。話說那個站會後悔，第二次經過它會收回100萬，第三次經過收回250萬，這樣的話你只需要經過一次就夠了，問題也是有解的。再比如說對於多權重圖，從A點出發經過B點到達C點的最短路線，就不是簡單的AB最短路線+BC最短路線了，說不定兩者有重合邊，第二次經過來個天價就傻眼了。其實這種圖貌似應該可以轉化成單權重圖的，我直覺估計啊，剛隨便想出這個問題，還沒去思考這個問題的解^_^

⑦ 關於Dijkstra演算法和Floyd演算法

Dijkstra 演算法：非負權重網路

Floyd 演算法 ： 不存在負環的網路 【允許存在負權重邊】

有專門的負環檢測演算法

⑧ Dijkstra's 最短路徑演算法能不能解這個含有負權重的問題

Dijkstra演算法當中將節點分為已求得最短路徑的集合（記為S）和未確定最短路徑的個集合（記為U），歸入S集合的節點的最短路徑及其長度不再變更，如果邊上的權值允許為負值，那麼有可能出現當與S內某點（記為a）以負邊相連的點（記為b）確定其最短路徑時，它的最短路徑長度加上這條負邊的權值結果小於a原先確定的最短路徑長度，而此時a在Dijkstra演算法下是無法更新的，由此便可能得不到正確的結果。求帶負權值邊的單源最短路徑可以用貝爾曼-福特演算法。