最短路徑演算法floyd

『壹』 為什麼floyd演算法可以計算負權值圖的最短路徑問題

弗洛伊德演算法：Dis(i,j) =min(Dis(i,j), Dis(i,k) + Dis(k,j)).
我是這么理解的，Dis(i,k)或Dis(k,j)可以有一條邊是負的，只要兩者之和不是負的就行，因為兩個和為負就會選取到這個組合，但是路徑的結果不應該是負的。Dijkstra中S(已求出解)中的每一個點解即最短路徑是已求出的,若存在負數路徑,可能存在已求出的解不是最優解.

『貳』 【數據結構】最短路徑之迪傑斯特拉(Dijkstra)演算法與弗洛伊德(Floyd)演算法

迪傑斯特拉(Dijkstra)演算法核心： 按照路徑長度遞增的次序產生最短路徑。

迪傑斯特拉(Dijkstra)演算法步驟：（求圖中v0到v8的最短路徑）並非一下子求出v0到v8的最短路徑，而是 一步一步求出它們之間頂點的最短路徑 ，過過程中都是 基於已經求出的最短路徑的基礎上，求得更遠頂點的最短路徑，最終得出源點與終點的最短路徑 。

弗洛伊德(Floyd)演算法是一個經典的 動態規劃演算法 。

『叄』 最短路徑的floyd演算法的時間復雜度

Floyd：每對節點之間的最短路徑。Floyd-Warshall演算法（Floyd-Warshall
algorithm）是解決任意兩點間的最短路徑的一種演算法，可以正確處理有向圖或負權的最短路徑問題，同時也被用於計算有向圖的傳遞閉包。Floyd-Warshall演算法的時間復雜度為O(N3)，空間復雜度為O(N2)。

先給出結論：

(1)當權值為非負時，用Dijkstra。

(2)當權值有負值，且沒有負圈，則用SPFA，SPFA能檢測負圈，但是不能輸出負圈。

(3)當權值有負值，而且可能存在負圈，則用BellmanFord，能夠檢測並輸出負圈。

(4)SPFA檢測負環：當存在一個點入隊大於等於V次，則有負環，後面有證明。

『肆』 a*演算法求最短路徑和floyd還有dijsktra演算法求最短路徑的區別

A*演算法是啟發式搜索，適合點對點的最短路徑，單源單匯的情況
Floyd是動態規劃的一種，可以求出任意兩點之間的最短路徑
Dijkstra是貪婪演算法的一種，求一點到其他所有點的最短路，即所謂的單源最短路演算法
從時間復雜度來說
Floyd是O(N^3)
Dijkstra是O(N^2)
而啟發式搜索就不好說了……
結果當然是一樣的，都是最短路，但是適用情形和時空開銷就不同了
舉例來說，你做任意兩點間最短路可以用N次Dijkstra或者1次Floyd，時間消耗一樣，顯然用後者，而如果你只用求兩點間的，用Floyd就不合算了

『伍』 floyd演算法求最短路徑怎麼用

Dijkstra演算法
1.定義概覽
Dijkstra(迪傑斯特拉)演算法是典型的單源最短路徑演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法是很有代表性的最短路徑演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。注意該演算法要求圖中不存在負權邊。
問題描述：在無向圖 G=(V,E) 中，假設每條邊 E[i] 的長度為 w[i]，找到由頂點 V0 到其餘各點的最短路徑。（單源最短路徑）

2.演算法描述
1)演算法思想：設G=(V,E)是一個帶權有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以後每求得一條最短路徑 , 就將加入到集合S中，直到全部頂點都加入到S中，演算法就結束了），第二組為其餘未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大於從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。
2)演算法步驟：
a.初始時，S只包含源點，即S＝{v}，v的距離為0。U包含除v外的其他頂點，即:U={其餘頂點}，若v與U中頂點u有邊，則<u,v>正常有權值，若u不是v的出邊鄰接點，則<u,v>權值為∞。
b.從U中選取一個距離v最小的頂點k，把k，加入S中（該選定的距離就是v到k的最短路徑長度）。
c.以k為新考慮的中間點，修改U中各頂點的距離；若從源點v到頂點u的距離（經過頂點k）比原來距離（不經過頂點k）短，則修改頂點u的距離值，修改後的距離值的頂點k的距離加上邊上的權。
d.重復步驟b和c直到所有頂點都包含在S中。

『陸』 最短路徑問題5種類型

最短路徑問題5種類型有Dijkstra演算法、A*演算法、SPFA演算法、Bellman-Ford演算法和Floyd-Warshall演算法，

擴展知識：

用於解決最短路徑問題的演算法被稱做「最短路徑演算法」，有時被簡稱作「路徑演算法」。最常用的路徑演算法有：
Dijkstra演算法、A*演算法、SPFA演算法、Bellman-Ford演算法和Floyd-Warshall演算法，本文主要介紹其中的三種。
最短路徑問題是圖論研究中的一個經典演算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。
演算法具體的形式包括：確定起點的最短路徑問題：即已知起始結點，求最短路徑的問題。
確定終點的最短路徑問題：與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同於把所有路徑方向反轉的確定起點的問題。
確定起點終點的最短路徑問題：即已知起點和終點，求兩結點之間的最短路徑。

『柒』 最短路徑法如何計算

最短路徑演算法有三種，Floyd，dijkstra，Bellman_Ford。其中，Floyd適合用於計算每兩點間的路徑，dijkstra適合稀疏圖，bellman則適合稠密圖中的已知起點終點，計算最短路徑的問題。時間復雜度，floyd演算法為n立方，dijk為n平方，bellman為n平方，其中n是點數。dijk可用堆維護，時間復雜度可減至nlogn，而bellman可用隊列維護，此方法於1994年被國人提出，命名比較土鱉叫SPFA(shortest path faster algorithm。。。)。至於如何計算，有了名字，搜一下就ok。

『捌』 弗洛伊德演算法可以解決無向圖最短路徑么

可以的，弗洛伊德演算法利用動態規劃解決了無向圖中任意兩個點之間的最短路徑，時間復雜度是O(n^3)，n是圖中點個數
同時可以使用狄傑斯卡拉演算法解決無向圖的最短路徑問題，他計算的是圖中指定點到其餘各點的最短路徑，時間復雜度是O(n^2)