一、負權形成環(huán)路的圖為什么不能用弗洛伊德算法求任意兩點之間的最短路徑

負權形成環(huán)路的圖,任意兩點間可能沒有最短路徑。例如負權環(huán)C，點A,B是C上的點，A可以在C中轉上任意圈后再沿C到B，這條路徑權值可以任意小。而Floyd算法可以給出網絡中任意兩個節(jié)點之間的最短路徑。

Floyd算法的基本思想

從任意節(jié)點A到任意節(jié)點B的最短路徑不外乎2種可能：

所以，我們假設dist(AB)為節(jié)點A到節(jié)點B的最短路徑的距離，對于每一個節(jié)點K，我們檢查dist(AK) + dist(KB) < dist(AB)是否成立，如果成立，證明從A到K再到B的路徑比A直接到B的路徑短，我們便設置 dist(AB) = dist(AK) + dist(KB)，這樣一來，當我們遍歷完所有節(jié)點K，dist(AB)中記錄的便是A到B的最短路徑的距離。

Floyd算法與Dijkstra算法的不同

Floyd算法是求任意兩點之間的距離，是多源最短路，而Dijkstra(迪杰斯特拉)算法是求一個頂點到其他所有頂點的最短路徑，是單源最短路。

Floyd算法屬于動態(tài)規(guī)劃，我們在寫核心代碼時候就是相當于推dp狀態(tài)方程，Dijkstra(迪杰斯特拉)算法屬于貪心算法。

Dijkstra(迪杰斯特拉)算法時間復雜度一般是o(n2),Floyd算法時間復雜度是o(n3),Dijkstra(迪杰斯特拉)算法比Floyd算法塊。

Floyd算法可以算帶負權的，而Dijkstra(迪杰斯特拉)算法是不可以算帶負權的。并且Floyd算法不能算負權回路。

延伸閱讀：

二、最短路徑問題（SPP）

最短路徑問題（Shortestpath problem）是圖論研究中的一個經典算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。

最短路徑問題根據初始條件的不同，可分為五種情況：

1）最短路徑問題：旨在尋找圖中兩點之間的最短路徑；

2）確定起點的最短路徑問題：即已知起點，求最短路徑的問題；

3）確定終點的最短路徑問題：與確定起點的問題相反，該問題是已知終點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉的確定起點的問題；

4）確定起點終點的最短路徑問題，即已知起點和終點，求兩點之間的最短路徑；

5）：全局最短路徑問題：求圖中任意兩點間的最短路徑。也可以合并為一種情況——全局最短路徑問題，只要求出全局最短路徑，那其余四種情況也已經包含在內了。

而計算最短路徑的常用算法有迪杰斯特拉算法、貝爾曼-福特算法、弗洛伊德算法等，下面小競將為大家一一介紹其基本概念、優(yōu)缺點、適用情況和案例分析。

迪杰斯特拉（Dijkstra）算法：用于解決從起點到其他各結點的最短路徑，解決的是有向圖中最短路徑問題。其主要特點是以初始點為中心向外層層擴展，直到擴展到終點為止，但也有圖中不能存在負權值的邊的限制。

貝爾曼-福特(Bellman–Ford)算法：用于解決從起點到其他各節(jié)點的最短距離。與迪杰斯特拉算法不同的是，貝爾曼-福特算法可支持存在負權重的情況，即打破了圖中不能存在負權值的邊的限制，其邊的權值可以為負數、實現(xiàn)簡單，但也存在時間復雜度過高的缺點。可對原始算法進行若干優(yōu)化，提高效率。貝爾曼-福特算法可用于解決以下問題：

1）從A出發(fā)是否存在到達各個節(jié)點的路徑(有計算出值當然就可以到達)；

2）從A出發(fā)到達各個節(jié)點最短路徑(時間最少、或者路徑最少等)；

3）圖中是否存在負環(huán)路（權重之和為負數）。