Floyd弗洛伊德

膜拜大佬，給大佬鞠躬鞠躬鞠躬。。。。。。。。。

Floyd算法?----解決頂點間的最短路徑：

過程：

如下：

初始化(沒有中轉點)：2個鄰接矩陣A和path，第一個是沒有中轉點的2個頂點之間的最短路徑(注意是2個頂點之間的直接路徑，中間沒有經過其他頂點，如果2個頂點比如A->B沒有直接路徑，A->C->B有路徑，此時也寫∞)，第2個是目前能找到的最短路徑中2個頂點之間的中轉點，剛開始沒有中轉點所以各2個頂點之間的中轉點都設為-1

中轉點加入V0頂點：在沒有加入V0中轉點時，A[2][1]即V2->V1路徑長度根據A鄰接矩陣知是∞，加入V0后即K=0，可以V2->V0,V0->V1，即A[2][0]+A[0][1]=5+6=11(根據A第一個鄰接矩陣得出)得出加了中轉點后V2->V1最短路徑由∞變為11，則修改A[2][1]即第一個鄰接矩陣V2->V1最短路徑為11，修改第二個鄰接矩陣V2->V1中轉點為0，所有的頂點都需要加入以上判斷，然后修改A和Path,目前看只有V2、V1頂點需要(A(0)[2][1]=11即加入了0號中轉點的V2->V1的最短路徑長度為11，path(0)[2][1]=0，即當前的V2->V1最短路徑長度加入了0號中轉點，每次都要判斷未加入中轉點的最小路徑長度>加入了中轉點之后的最小路徑長度，只有滿足這個式子才會修改A和Path)

中轉點加入V1頂點：在沒有加入V1中轉點時，V0->V2路徑長度是13，加入后V0->V1->V2即6+4=10，加入后值小滿足規則條件A(0)[0][2]>A[0][0][1]+A(1)[1][2]，修改A(1)[0][2]=10，path(1)[0][2]=1,其他頂點無需更改，加入中轉點后路徑沒有變化

中轉點加入V2頂點：在沒有加入V2中轉點時，V1->V0路徑長度是10，加入后V1->V2->V0即4+5=9，加入后值小滿足規則條件A(1)[1][2]>A(1)[1][2]+A(1)[2][0]，修改A(2)[1][0]=9，path(2)[1][0]=2

path寫的是中轉點，把誰加入了中轉點對應的path路徑上的值就寫誰，A寫的是最短路徑長度

經過n(頂點個數)輪中轉之后得到A(n-1)path(n-1)

如下：由A(n-1)即A(2)得，V1->V2最短路徑是4，由path(2)得V1->V2是-1，即V1->V2最短路徑4沒有經過中轉點，即為V1->V2，V0->V2最短路徑是10，由path(2)得V1->V2是1，即V0->V2最短路徑10經過中轉點1，即為V0->V1->V2即V0_V1_V2

代碼如下：?

準備一個圖的鄰接矩陣A+path矩陣初始值都設為-1，開始每循環一次增加一個中轉點，每增加一個中轉點遍歷一次A鄰接矩陣(遍歷行和列)，看加了中轉點之后的路徑長度和不加誰小，如果加了小更新鄰接矩陣A最短路徑長度和path中轉點

時間復雜度:要根據頂點個數遍歷3次即O(|V3|)

空間復雜度：矩陣的存儲空間行和列即O(|V2|)

5個頂點例子：

中轉點V0:沒有需要更新的

中轉點V1：既然是V1作為中間點出現，那必然要找指向V1的點作為起點V2和從V1指出的點(此時不要直接看圖，要看鄰接矩陣)V3、V4,可得V1作為中間點、V2作為起點有2條路徑，V2->V1->V3=1+1=2，但是V2->V3沒有直接路徑即∞，修改A(1)[2][3]=2,path(1)[2][3]=1，另一條V2->V1->V4=1+5=6，V2直接到V4=7，則修改A(1)[2][4]=6,path(1)[2][4]=1【修改對應path上的橫縱坐標確定的值為1】

中轉點V2：既然是V2作為中間點出現，那必然要找指向V2的點作為起點V0和從V2指出的點(直接看鄰接矩A中V2作為橫坐標V2所在行有值的點，不要看圖！！！)即V1、V3(V2->V3在圖中并沒有直接指向，但是在鄰接矩陣A中(2,3)=2,是因為上一步已經加入了中轉點V1，V2->V3沒有直接路徑，但是可以V2->V1->V3=2有中轉點路徑，即在使用中轉點V2時也使用了中轉點V1的結果，在已經有了一個中轉點的情況下，計算某2個頂點最短路徑時也要看鄰接矩陣而不是看圖上邊的權值！！！)、V4,可得V2作為中間點、V0作為起點有3條路徑，V0->V2->V1=1+1=2(鄰接矩陣中V0->V2是1，V2->V1是1) <V0->V1是∞，修改A(2)[0][1]=2,path(2)[0][1]=2，另一條V0->V2->V4=1+6=8(注意不要看圖上的權值，看鄰接矩陣中的最短路徑！！！否則就變成了1+7=8，鄰接矩陣A上V0->V2=1,V2->V4=6即1+6=7)，V0直接到V4=10，則修改A(2)[0][4]=8,path(2)[0][4]=2，另一條V0->V2->V3=1+2=3(鄰接矩陣A上V0->V2=1,V2->V3=2即1+2=3) < V0->V3=∞，則修改A(2)[0][3]=3,path(2)[0][3]=2【修改對應path上的橫縱坐標確定的值為2】

中轉點V3：上同

中轉點V4：上同

根據最終中轉矩陣找路徑：

如下為最終中轉的A和path，找V0->V4路徑，由A知V0->V4最短路徑為4，由path知V0->V4中轉點是3，再由A知V3->V4最短路徑1，由path知V3->V4=-1即V3和V4之間沒有中轉點，再看V0->V3，由A知V0->V3最短路徑3，由path知V0->V3=2級V0->V3中轉點V2，即V0->V2->V3，看V0->V2，由A知V0->V2最短路徑1，由path知V0->V2=-1即V0->V2沒有中轉點，再看V2->V3，由A知V2->V3最短路徑2，由path知V2->V3=1即V2->V3有中轉點V1，即V2->V1->V3，看V2->V1，由A知V2->V1最短路徑1，由path知V2->V1=-1即V2->V1沒有中轉點，再看V1->V3，由A知V1->V3最短路徑1，由path知V1->V3=-1即V1->V3沒有中轉點

V0->V3->V4? 第一輪? ?V3->V4不動路徑為1，看V0->V3有哪些中轉點

V0->V2->V3->V4第二輪? V0->V2不動路徑1、V3->V4不動路徑1，看V2->V3有哪些中轉點

V0->V2->V1->V3->V4第三輪? V0->V2、V2->V1、V1->V3、V3->V4不動路徑1，各路徑無中轉點

練習：

弗洛伊德算法可解決帶負權值，但不能解決帶回路的負權值

??

知識回顧：

?

下次再見?

?