最短路徑的floyd演算法

❶ 最短路徑演算法

最短路徑演算法一般有Dijkstra演算法，Bellman-Ford演算法，Floyd演算法和SPFA演算法等。

從某頂點出發，沿圖的邊到達另一頂點所經過的路徑中，各邊上權值之和最小的一條路徑叫做最短路徑。解決最短路的問題有以下演算法，Dijkstra演算法，Bellman-Ford演算法，Floyd演算法和SPFA演算法等。

最短路徑演算法問題：

最短路徑問題是圖論研究中的一個經典演算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。演算法具體的形式包括：

（1）確定起點的最短路徑問題- 即已知起始結點，求最短路徑的問題。適合使用Dijkstra演算法。

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

（3）確定起點終點的最短路徑問題- 即已知起點和終點，求兩結點之間的最短路徑。

（4）全局最短路徑問題- 求圖中所有的最短路徑。適合使用Floyd-Warshall演算法。

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

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

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

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

❸ 用弗洛伊德演算法求最短路徑

是地信的題吧，先給你說v1怎麼求，
先找出v1能去的最近的點，為V2，
如果S1i>S12+S2i
修改V1到Vi的距離為S12+S2i
然後去掉V2，在其餘的點中找距V1最近的，按上面的方法修改
最後得到V1與其他各點的最短距離
同樣的方法求出到其他點的最短距離

❹ 最短路徑的floyd演算法的時間復雜度

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

先給出結論：

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

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

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

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

❺ floyd演算法求最短路徑

Floyd演算法適用於APSP(AllPairsShortestPaths)，是一種動態規劃演算法，稠密圖效果最佳，邊權可正可負。此演算法簡單有效，由於三重循環結構緊湊，對於稠密圖，效率要高於執行|V|次Dijkstra演算法。

優點：容易理解，可以算出任意兩個節點之間的最短距離，代碼編寫簡單

缺點：時間復雜度比較高，不適合計算大量數據。

時間復雜度:O(n^3)；空間復雜度:O(n^2)；

任意節點i到j的最短路徑兩種可能：

直接從i到j；
從i經過若干個節點k到j。
map（i，j）表示節點i到j最短路徑的距離，對於每一個節點k，檢查map（i，k）+map（k，j）小於map(i，j),如果成立，map（i，j） = map（i，k）+map（k，j）；遍歷每個k，每次更新的是除第k行和第k列的數。

步驟：

第1步：初始化map矩陣。
矩陣中map[i][j]的距離為頂點i到頂點j的權值；

如果i和j不相鄰，則map[i][j]=∞。

如果i==j，則map[i][j]=0;
第2步：以頂點A(假設是第1個頂點)為中介點，若a[i][j] > a[i][1]+a[1][j]，則設置a[i][j]=a[i][1]+a[1][j]。

❻ Floyd-Warshall 全源最短路徑演算法

前言

全源最短路徑是相對單源最短路徑而言的，用於查找圖中所有點對其它點的最短路徑。

Floyd-Warshall演算法適用於存在負權重但不存在負迴路的圖，稠密圖，它的運行時間為O(n ³ )。

它的實質是動態規劃。

本文以下圖為示例：

最優子結構

具體描述為：對於給定的帶權圖 G = (V, E)，設 p = <v ₁ , v ₂ , …,v _k > 是從 v ₁ 到 v _k 的最短路徑，那麼對於任意 i 和 j，1 ≤ i ≤ j ≤ k，p _ij = <v _i , v _i+1 , …, v _j > 為 p 中頂點 v _i 到 v _j 的子路徑，那麼 p _ij 是頂點 v _i 到 v _j 的最短路徑。

設帶權圖 G = (V, E) 中的所有頂點 V = {1, 2, . . . , n}，考慮一個頂點子集 {1, 2, . . . , k}。對於任意對頂點 i, j，考慮從頂點 i 到 j 的所有路徑的中間頂點都來自該子集 {1, 2, . . . , k}，設 p 是該子集中的最短路徑。Floyd-Warshall 演算法描述了 p 與 i, j 間最短路徑及中間頂點集合 {1, 2, . . . , k - 1} 的關系，該關系依賴於 k 是否是路徑 p 上的一個中間頂點。

設d ^(k) _ij 為從結點i到結點j的所有中間結點全部取自於集合 {1, 2, . . . , k} 的一條最短路徑的權重。當k=0時，即最短路徑中不包含任何中間結點，此時的最短路徑就是權重本身值。

具體實現

根據上文分析，可以遍歷k值，將最短路徑分成兩段，如果p _ik 和p _kj 之和少於p _ij ，則認為k是ij最短路徑上的中間節點，更新最短路徑值。

❼ 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中。

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

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

❾ floyd-warshanll演算法是什麼啊

Floyd-Warshall演算法是解決任意兩點間的最短路徑的一種演算法。
Floyd-Warshall演算法的描述如下： for k:=1 to n do for i:=1 to n do for j:=1 to n do if dist[i,k]+dist[k,j]<dist[i,j] then dist[i,j]:=dist[i,k]+dist[k,j];
Floyd-Warshall 演算法用來找出每對點之間的最短距離。它需要用鄰接矩陣來儲存邊，這個演算法通過考慮最佳子路徑來得到最佳路徑。
注意單獨一條邊的路徑也不一定是最佳路徑。
從任意一條單邊路徑開始。所有兩點之間的距離是邊的權，或者無窮大，如果兩點之間沒有邊相連。
對於每一對頂點 u 和 v，看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。
不可思議的是，只要按排適當，就能得到結果。 // dist(i,j) 為從節點i到節點j的最短距離 For i←1 to n do For j←1 to n do dist(i,j) = weight(i,j) For k←1 to n do // k為「媒介節點」 For i←1 to n do For j←1 to n do if (dist(i,k) + dist(k,j) < dist(i,j)) then // 是否是更短的路徑？ dist(i,j) = dist(i,k) + dist(k,j)
這個演算法的效率是O(V^3)。它需要鄰接矩陣來儲存圖。
這個演算法很容易實現，只要幾行。
即使問題是求單源最短路徑，還是推薦使用這個演算法，如果時間和空間允許(只要有放的下鄰接矩陣的空間，時間上就沒問題)。
計算每一對頂點間的最短路徑（floyd演算法）
【例題】設計公共汽車線路(1) 現有一張城市地圖，圖中的頂點為城市，有向邊代表兩個城市間的連通關系，邊上的權即為距離。現在的問題是，為每一對可達的城市間設計一條公共汽車線路，要求線路的長度在所有可能的方案里是最短的。
輸入： n (城市數，1≤n≤20) e (有向邊數1≤e≤210) 以下e行，每行為邊（i,j）和該邊的距離wij（1≤i,j≤n）
輸出： k行，每行為一條公共汽車線路
分析：本題給出了一個帶權有向圖，要求計算每一對頂點間的最短路徑。這個問題雖然不是圖的連通性問題，但是也可以借鑒計算傳遞閉包的思想：在枚舉途徑某中間頂點k的任兩個頂點對i和j時，將頂點i和頂點j中間加入頂點k後是否連通的判斷，改為頂點i途徑頂點k至頂點j的路徑是否為頂點i至頂點j的最短路徑（1≤i，j，k≤n）。 顯然三重循環即可計算出任一對頂點間的最短路徑。設 n—有向圖的結點個數； path—最短路徑集合。其中path[i，j]為vi至vj的最短路上vj的前趨結點序號(1≤i，j≤n)； adj—最短路徑矩陣。初始時為有向圖的相鄰矩陣
我們用類似傳遞閉包的計算方法反復對adj矩陣進行運算，最後使得adj成為存儲每一對頂點間的最短路徑的矩陣 (1≤i，j≤n) Var adj：array[1‥n，1‥n] of real； path：array[1‥n，1‥n] of 0‥n；
計算每一對頂點間最短路徑的方法如下：
首先枚舉路徑上的每一個中間頂點k（1≤k≤n）；然後枚舉每一個頂點對（頂點i和頂點j，1≤i，j≤n）。如果i頂點和j頂點間有一條途徑頂點k的路徑，且該路徑長度在目前i頂點和j頂點間的所有條途徑中最短，則該方案記入adj[i，j]和path[i，j] adj矩陣的每一個元素初始化為∞；
for i←1 to n do {初始時adj為有向圖的相鄰矩陣，path存儲邊信息} for j←1 to n do if wij<>0 then begin adj[i，j]←wij； path[i，j]←j； end{then} else path[i，j]←0； for k←1 to n do {枚舉每一個中間頂點} for i←1 to n do {枚舉每一個頂點對} for j←1 to n do if adj[i，k]+adj[k，j]<adj[i，j]{若vi經由vk 至vj的路徑目前最優，則記下} then begin adj[i，j]←adj[i，k]+adj[k，j]； path[i，j]←path[k，j]； end，{then} 計算每一對頂點間最短路徑時間復雜度為W(n3)。演算法結束時，由矩陣path可推知任一結點對i、j之間的最短路徑方案是什麼 Procere print(i，j)； begin if i=j then 輸出i else if path[i，j]=0 then 輸出結點i與結點j之間不存在通路 else begin print (i，path[i，j])； {遞歸i頂點至j頂點的前趨頂點間的最短路徑} 輸出j； end；{else} end；{print} 由此得出主程序 距離矩陣w初始化為0； 輸入城市地圖信息（頂點數、邊數和距離矩陣w）； 計算每一對頂點間最短路徑的矩陣path； for i←1 to n do {枚舉每一個頂點對} for j←1 to n do if path[i，j]<>0 {若頂點i可達頂點j，則輸出最短路徑方案} then begin print（i，j）； writeln； end；{then}