warshall演算法圖解

1. Warshall演算法求傳遞閉包，Python語言~

def __warshall(self, a):
assert (len(row) == len(a) for row in a)
n = len(a)
#請在下面編程實現Roy-Warshall求傳遞閉包的演算法
#參數a：為一個關系矩陣
# 請刪除pass後編程實現該方法功能
for i in range(n) :
for j in range(n):
if a[j][i] == 1:
for k in range(n):
a[j][k] = a[j][k] | a[i][k]
# 請在上面編寫程序，不要修改下面代碼
return a

2. Warshall演算法的演算法介紹

1、引言
Warshall在1962年提出了一個求關系的傳遞閉包的有效演算法。其具體過程如下，設在n個元素的有限集上關系R的關系矩陣為M：
（1）置新矩陣A=M;
（2）置k=1;
（3）對所有i如果A[i,k]=1，則對j=1..n執行：
A[i,j]←A[i,j]∨A[k,j];
（4）k增1;
（5）如果k≤n，則轉到步驟（3），否則停止。
所得的矩陣A即為關系R的傳遞閉包t(R)的關系矩陣。
在左孝凌等編著的《離散數學》中提到了該演算法，但並未對此演算法作出解釋。下面本文將對該演算法的思想作出一種比較通俗的解說。
2、對Warshall演算法的解說
設關系R的關系圖為G，設圖G的所有頂點為v1,v2,…,vn，則t(R)的關系圖可用該方法得到：若G中任意兩頂點vi和vj之間有一條路徑且沒有vi到vj的弧，則在圖G中增加一條從vi到vj的弧，將這樣改造後的圖記為G』，則G』即為t(R)的關系圖。G』的鄰接矩陣A應滿足：若圖G中存在從vi到vj路徑，即vi與vj連通，則A[i,j]=1，否則A[i,j]=0。
這樣，求t(R)的問題就變為求圖G中每一對頂點間是否連通的問題。
定義一個n階方陣序列A(0),A(1),A(2),…,A(n)，每個方陣中的元素值只能取0或1。A(m)[i,j]=1表示存在從vi到vj且中間頂點序號不大於m的路徑（m=1..n），A(m)[i,j]=0表示不存在這樣的路徑。而A(0)[i,j]=1表示存在從vi到vj的弧，A(0)[i,j]=0表示不存在從vi到vj的弧。
這樣，A(n)[i,j]=1表示vi與vj連通，A(n)[i,j]=0表示vi與vj不連通。故A(n)即為t(R)的關系矩陣。
那麼應如何計算方陣序列A(0),A(1),A(2),…,A(n)呢？
很顯然，A(0)=M（M為R的關系矩陣）。
若A(0)[i,1]=1且A(0)[1,j]=1，或A(0)[i,j]=1，當且僅當存在從vi到vj且中間頂點序號不大於1的路徑，此時應將A(1)[i,j]置為1，否則置為0。
一般地，若A(k-1)[i,k]=1且A(k-1)[k,j]=1，或A(k-1)[i,j]=1，當且僅當存在從vi到vj且中間頂點序號不大於k的路徑，此時應將A(k)[i,j]置為1，否則置為0（k=1..n）。用公式表示即為：
A (k)[i,j]=(A(k-1)[i,k]∧A(k-1)[k,j])∨A(k-1)[i,j] i,j,k=1..n
這樣，就可得計算A(k)的方法：先將A(k)賦為A(k-1)；再對所有i=1..n，若A(k)[i,k]=1（即A(k-1)[i,k]=1），則對所有j=1..n，執行：
A (k)[i,j]←A(k)[i,j]∨A(k-1)[k,j]
但這與前述Warshall演算法中的第（3）步還有一定距離。若將上式改為：
A(k)[i,j]←A(k)[i,j]∨A(k)[k,j] （即把A(k-1)[k,j]改為A(k)[k,j]）
就可將上標k去掉，式子就可進一步變為：
A[i,j]←A[i,j]∨A[k,j]
這樣可以只用存儲一個n階方陣的空間完成計算，且與前述Warshall演算法中第（3）步的式子一致。那麼，可不可以把A(k-1)[k,j]改為A(k)[k,j]呢？答案是肯定的。下面將證明在計算A(k)的過程中A(k-1)[k,j]與A(k)[k,j]相等（A(k)被賦初值A(k-1)後）。考察計算A(k)的方法 只有當i=k時A(k)[k,j]的值才有可能改變，此時將式A(k)[i,j]←A(k)[i,j]∨A(k-1)[k,j]中的i換為k，得A(k)[k,j]←A(k)[k,j]∨A(k-1)[k,j]，對某一j，執行該式的賦值操作前A(k)[k,j]=A(k-1)[k,j]，因為計算A(k)開始時A(k)被賦為A(k-1)，故它們相或的結果等於A(k-1)[k,j]，故賦值操作不改變A(k)[k,j]的值。這樣，就沒有操作會改變A(k)[k,j]的值，故A(k-1)[k,j]與A(k)[k,j]相等。
綜上，就可得到計算A(n)的演算法，且該演算法與前述的Warshall演算法完全一致。
由上面的分析，不難看出，Warshall演算法類似於求圖中每對頂點間最短路徑的Floyd演算法。其實，用Floyd演算法也能求關系的傳遞閉包，方法為令關系R的關系圖G中的每條弧的權值都為1，這樣得一有向網G1，設G1的鄰接矩陣為D(-1)（若vi無自迴路，則D(-1)(i,i)=∞），對G1用Floyd演算法求其每對頂點間最短路徑，得結果矩陣D(n-1)。因若G中vi與vj連通，當且僅當D(n-1)[i,j]≠∞，故將矩陣D中的∞都改為0，其它值都改為1，得矩陣A，則矩陣A即為t(R)的關系矩陣。Floyd演算法和Warshall演算法的時間復雜度都為O(n3)，但明顯用Floyd演算法求關系的傳遞閉包繞了彎子。
參考文獻：
[1]左孝凌，李為鑒，劉永才，《離散數學》，上海：上海科學技術文獻出版社，1982
[2]嚴蔚敏，吳偉民，《數據結構 C語言版》，北京：清華大學出版社，1997

3. 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}

4. Floyd演算法的演算法過程

1，從任意一條單邊路徑開始。所有兩點之間的距離是邊的權，如果兩點之間沒有邊相連，則權為無窮大。
2，對於每一對頂點 u 和 v，看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比已知的路徑更短。如果是更新它。
把圖用鄰接矩陣G表示出來，如果從Vi到Vj有路可達，則G[i,j]=d，d表示該路的長度；否則G[i,j]=無窮大。定義一個矩陣D用來記錄所插入點的信息，D[i,j]表示從Vi到Vj需要經過的點，初始化D[i,j]=j。把各個頂點插入圖中，比較插點後的距離與原來的距離，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值變小，則D[i,j]=k。在G中包含有兩點之間最短道路的信息，而在D中則包含了最短通路徑的信息。
比如，要尋找從V5到V1的路徑。根據D，假如D(5,1)=3則說明從V5到V1經過V3，路徑為{V5,V3,V1}，如果D(5,3)=3，說明V5與V3直接相連，如果D(3,1)=1，說明V3與V1直接相連。

5. 最短路徑 | 深入淺出Dijkstra演算法（一）

上次我們介紹了神奇的只有 五行的 Floyd-Warshall 最短路演算法 ，它可以方便的求得 任意兩點的最短路徑， 這稱為 「多源最短路」。

這次來介紹 指定一個點（源點）到其餘各個頂點的最短路徑， 也叫做 「單源最短路徑」。 例如求下圖中的 1 號頂點到 2、3、4、5、6 號頂點的最短路徑。

與 Floyd-Warshall 演算法一樣，這里仍然 使用二維數組 e 來存儲頂點之間邊的關系， 初始值如下。

我們還需要用 一個一維數組 dis 來存儲 1 號頂點到其餘各個頂點的初始路程， 我們可以稱 dis 數組為 「距離表」， 如下。

我們將此時 dis 數組中的值稱為 最短路的「估計值」。

既然是 求 1 號頂點到其餘各個頂點的最短路程， 那就 先找一個離 1 號頂點最近的頂點。

通過數組 dis 可知當前離 1 號頂點最近是 2 號頂點。 當選擇了 2 號頂點後，dis[2]的值就已經從「估計值」變為了「確定值」， 即 1 號頂點到 2 號頂點的最短路程就是當前 dis[2]值。

為什麼呢？你想啊， 目前離 1 號頂點最近的是 2 號頂點，並且這個圖所有的邊都是正數，那麼肯定不可能通過第三個頂點中轉，使得 1 號頂點到 2 號頂點的路程進一步縮短了。 因此 1 號頂點到其它頂點的路程肯定沒有 1 號到 2 號頂點短，對吧 O(∩_∩)O~

既然選了 2 號頂點，接下來再來看 2 號頂點 有哪些 出邊 呢。有 2->3 和 2->4 這兩條邊。

先討論 通過 2->3 這條邊能否讓 1 號頂點到 3 號頂點的路程變短。 也就是說現在來比較 dis[3] 和 dis[2]+e[2][3] 的大小。其中 dis[3]表示 1 號頂點到 3 號頂點的路程，dis[2]+e[2][3]中 dis[2]表示 1 號頂點到 2 號頂點的路程，e[2][3]表示 2->3 這條邊。所以 dis[2]+e[2][3]就表示從 1 號頂點先到 2 號頂點，再通過 2->3 這條邊，到達 3 號頂點的路程。

我們發現 dis[3]=12，dis[2]+e[2][3]=1+9=10，dis[3]>dis[2]+e[2][3]，因此 dis[3]要更新為 10。這個過程有個專業術語叫做 「鬆弛」 。即 1 號頂點到 3 號頂點的路程即 dis[3]，通過 2->3 這條邊 鬆弛成功。 這便是 Dijkstra 演算法的主要思想： 通過 「邊」 來鬆弛 1 號頂點到其餘各個頂點的路程。

同理通過 2->4（e[2][4]），可以將 dis[4]的值從 ∞ 鬆弛為 4（dis[4]初始為 ∞，dis[2]+e[2][4]=1+3=4，dis[4]>dis[2]+e[2][4]，因此 dis[4]要更新為 4）。

剛才我們對 2 號頂點所有的出邊進行了鬆弛。鬆弛完畢之後 dis 數組為：

接下來，繼續在剩下的 3、4、5 和 6 號頂點中，選出離 1 號頂點最近的頂點。通過上面更新過 dis 數組，當前離 1 號頂點最近是 4 號頂點。此時，dis[4]的值已經從「估計值」變為了「確定值」。下面繼續對 4 號頂點的所有出邊（4->3，4->5 和 4->6）用剛才的方法進行鬆弛。鬆弛完畢之後 dis 數組為：

繼續在剩下的 3、5 和 6 號頂點中，選出離 1 號頂點最近的頂點，這次選擇 3 號頂點。此時，dis[3]的值已經從「估計值」變為了「確定值」。對 3 號頂點的所有出邊（3->5）進行鬆弛。鬆弛完畢之後 dis 數組為：

繼續在剩下的 5 和 6 號頂點中，選出離 1 號頂點最近的頂點，這次選擇 5 號頂點。此時，dis[5]的值已經從「估計值」變為了「確定值」。對5號頂點的所有出邊（5->4）進行鬆弛。鬆弛完畢之後 dis 數組為：

最後對 6 號頂點的所有出邊進行鬆弛。因為這個例子中 6 號頂點沒有出邊，因此不用處理。 到此，dis 數組中所有的值都已經從「估計值」變為了「確定值」。

最終 dis 數組如下，這便是 1 號頂點到其餘各個頂點的最短路徑。

OK，現在來總結一下剛才的演算法。 Dijkstra演算法的基本思想是：每次找到離源點（上面例子的源點就是 1 號頂點）最近的一個頂點，然後以該頂點為中心進行擴展，最終得到源點到其餘所有點的最短路徑。

基本步驟如下：

在 博客 中看到兩個比較有趣的問題，也是在學習Dijkstra時，可能會有疑問的問題。

當我們看到上面這個圖的時候，憑借多年對平面幾何的學習，會發現在「三角形ABC」中，滿足不了 構成三角形的條件(任意兩邊之和大於第三邊)。 納尼，那為什麼圖中能那樣子畫？

還是「三角形ABC」，以A為起點，B為終點，如果按照平面幾何的知識， 「兩點之間線段最短」， 那麼，A到B的最短距離就應該是6(線段AB)，但是，實際上A到B的最短距離卻是3+2=5。這又怎麼解釋？

其實，之所以會有上面的疑問，是因為 對邊的權值和邊的長度這兩個概念的混淆， 。之所以這樣畫，也只是為了方便理解（每個人寫草稿的方式不同，你完全可以用別的方式表示，只要便於你理解即可）。

PS：數組實現鄰接表可能較難理解，可以看一下 這里

參考資料：

Dijkstra演算法是一種基於貪心策略的演算法。每次新擴展一個路程最短的點，更新與其相鄰的點的路程。當所有邊權都為正時，由於不會存在一個路程更短的沒擴展過的點，所以這個點的路程永遠不會再被改變，因而保證了演算法的正確性。

根據這個原理， 用Dijkstra演算法求最短路徑的圖不能有負權邊， 因為擴展到負權邊的時候會產生更短的路徑，有可能破壞了已經更新的點路徑不會發生改變的性質。

那麼，有沒有可以求帶負權邊的指定頂點到其餘各個頂點的最短路徑演算法（即「單源最短路徑」問題）呢？答案是有的， Bellman-Ford演算法 就是一種。（我們已經知道了 Floyd-Warshall 可以解決「多源最短路」問題，也要求圖的邊權均為正）

通過 鄰接矩陣 的Dijkstra時間復雜度是 。其中每次找到離 1 號頂點最近的頂點的時間復雜度是 O(N)，這里我們可以用 優先隊列（堆） 來優化，使得這一部分的時間復雜度降低到 。這個我們將在後面討論。

6. floyd演算法能不能保證有最優解

Floyd演算法又稱為弗洛伊德演算法，插點法，是一種用於尋找給定的加權圖中頂點間最短路徑的演算法。

演算法過程:

把圖用鄰接距陣G表示出來，如果從Vi到Vj有路可達，則G[i,j]=d，d表示該路的長度；否則G[i,j]=空值。

定義一個距陣D用來記錄所插入點的信息，D[i,j]表示從Vi到Vj需要經過的點，初始化D[i,j]=j。
把各個頂點插入圖中，比較插點後的距離與原來的距離，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值變小，則D[i,j]=k。

在G中包含有兩點之間最短道路的信息，而在D中則包含了最短通路徑的信息。
比如，要尋找從V5到V1的路徑。根據D，假如D(5,1)=3則說明從V5到V1經過V3，路徑為{V5,V3,V1}，如果D(5,3)=3，說明V5與V3直接相連，如果D(3,1)=1，說明V3與V1直接相連。

7. Warshall演算法求傳遞閉包

#include <stdio.h>
#include <stdlib.h>
#define N 20
#define M 20

main()
{
int i,j,k,m,n;
int r1[M],r2[M],a[N],mr[N][N]={0};

FILE * fp;
printf("程序自動調用c:/stone2.txt文件內相應數據\n");
fp=fopen("c:\\stone2.txt","r");
fscanf(fp,"%d",&n); /*讀取集合元素個數*/
for(i=0;i<n;i++) /*讀取集合元素*/
fscanf(fp,"%d",&a[i]);
fscanf(fp,"%d",&m); /*讀取關系個數*/
for(k=0;k<m;k++)
fscanf(fp,"%d,%d",&r1[k],&r2[k]); /*讀取關系*/

fclose(fp);

printf("自反閉包r(R):\n{");
for(i=0;i<n;i++) printf("<%d,%d>,",a[i],a[i]); /*輸出自反閉包*/
for(k=0;k<m;k++)
{
if(r1[k]!=r2[k]) printf("<%d,%d>,",r1[k],r2[k]);
else continue;
}
printf("\b}\n");

printf("對稱閉包s(R):\n{"); /*輸出對稱閉包*/
for(k=0;k<m;k++)
{
if(r1[k]!=r2[k]) printf("<%d,%d>,<%d,%d>,",r1[k],r2[k],r2[k],r1[k]);
else printf("<%d,%d>,",r1[k],r2[k]);
}
printf("\b}\n");

k=0;
for(i=0;i<n,k<m;i++)
{
if(r1[k]!=a[i]) continue;
else
{
for(j=0;j<n,k<m;j++) /*關系轉換成矩陣*/
{
if(r2[k]!=a[j]) continue;
else
{
mr[i][j]=1;
k++; i=0;j=0;
break;
}
}
}
}

printf("關系所對應的關系矩陣:\n");
for(i=0;i<n;i++)
{ /*列印關系矩陣*/
for(j=0;j<n;j++)
printf("%5d",mr[i][j]);
printf("\n");
}
for(k=0;k<n;k++)
for(i=0;i<n;i++) /*warshall*/
for(j=0;j<n;j++)
mr[i][j]+=mr[i][j]+mr[i][k]*mr[k][j];

for(i=0;i<n;i++)
for(j=0;j<n;j++)
{ /*把mr[]非0項賦值為1*/
if(!mr[i][j]) continue;
else mr[i][j]=1;
}

printf("傳遞閉包對應關系矩陣:\n");
for(i=0;i<n;i++)
{ /*輸出傳遞閉包對應的關系矩陣*/
for(j=0;j<n;j++)
printf("%5d",mr[i][j]);
printf("\n");
}

system("PAUSE");

}
自己寫的,三個閉包都有,包括傳遞閉包,看注釋就知道了,還是用文件讀寫,方便數據輸入

8. 最短路徑的解決方法

用於解決最短路徑問題的演算法被稱做「最短路徑演算法」， 有時被簡稱作「路徑演算法」。 最常用的路徑演算法有：
Dijkstra演算法
SPFA演算法Bellman-Ford演算法
Floyd演算法Floyd-Warshall演算法
Johnson演算法
A*演算法
所謂單源最短路徑問題是指：已知圖G=（V，E），我們希望找出從某給定的源結點S∈V到V中的每個結點的最短路徑。
首先，我們可以發現有這樣一個事實：如果P是G中從vs到vj的最短路，vi是P中的一個點，那麼，從vs沿P到vi的路是從vs到vi的最短路。