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

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

Floyd算法的基本思想

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

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

Floyd算法與Dijkstra算法的不同

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

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

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

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

延伸閱讀：

二、最短路徑問題（SPP）

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

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

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

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

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

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

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

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

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

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

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

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

3）圖中是否存在負環路（權重之和為負數）。