一鬓椭、概述
當我們要求一個帶權有向圖中的所有點對的最短路徑時蒿讥，我們或許想到之前學的Dijkstra算法溉浙，但這個算法是算一個點到其他點的最短距離的萍歉，如果要求所有點對的最短路徑，我們需要對每一個點都是用這個算法光戈，時間復雜度是O（N^3）
我們給出另外一個算法控硼，FloydWarshall算法漱牵，雖然時間復雜度也為O（N^3）暇仲，但形式會簡單許多步做。其主要依賴于鄰接矩陣的更新來獲得最小值
二、實現方法
對于一個給定的圖奈附，我們初始化一個鄰接矩陣dist全度，表示的是與節(jié)點直接相連（或到達節(jié)點只需走一條邊）的節(jié)點的距離值，還有一個path數據表示從某節(jié)點到這個節(jié)點的距離路徑桅狠。
這兩個矩陣是一一對應的讼载。
第一次迭代，我們考察兩個節(jié)點經轉另一個節(jié)點后的距離是否會縮短中跌，我們先看經轉a節(jié)點，經過循環(huán)發(fā)現c經轉a到b的距離可以縮短菇篡，于是我們更新兩個數組
第二次迭代漩符，我們經轉b，于是發(fā)現a經轉b到c可縮短驱还，更新
第三次嗜暴，經轉c，發(fā)現可以议蟆，更新之
小練習
答案
三闷沥、規(guī)律
拿第一次迭代做例子，我們發(fā)現dist數組的更新是有規(guī)律可循的咐容，就用之前的數組的 i j 的值比較i 與 k （這里的k是我們之前說的經轉的節(jié)點舆逃，剛好和下表對上）、k 和 j 的距離之和的值，
取小的那一個放入新的距離數組
我們發(fā)現路狮，這個規(guī)律應該是正確的虫啥，于是可以總結如下：
注：arc矩陣是鄰接矩陣
以下有代碼實現。
偽代碼：
可見奄妨，我們更新數組的過程涂籽，需要有3重循環(huán)，第一重是依次對中轉節(jié)點的選擇砸抛，第二评雌、三重是循環(huán)二維數組，里面的代碼就是對距離進行判斷并進行更新直焙。
使用數字表示path數組
當然景东，我們可以不用字符串來表明最短路徑，我們可以用數字來直接表示箕般。
然后我們進行第一次迭代，雖然矩陣沒變化丝里，但這個矩陣的意義是發(fā)生變化了的曲初，因為經轉了 1 節(jié)點
然后進行第二次迭代，我們發(fā)現a13比a12+a23的值大杯聚，所以更新臼婆，并在P數組中記錄路徑
（注意我們這里索引以1開始，不是0；仙堋）
繼續(xù)颁褂，我們進行第三次迭代
第4次
第5次，發(fā)現不變傀广。
因為就5個節(jié)點颁独，已經循環(huán)完了，所以我們結束并得到最終結果
A數組的獲取方法和之前講的是一樣的
那我們怎么通過P數組找到路徑呢伪冰？
假如要找從1節(jié)點到5節(jié)點的路徑：
首先找p15誓酒，發(fā)現是4，可知其中有4中轉贮聂；
然后找p14靠柑，看看從1到4是否有中轉，發(fā)現沒有吓懈；
再找p45，發(fā)現有3中轉耻警；
此時我們還要找p43隔嫡，p35甸怕，發(fā)現沒有值，說明沒有中轉了畔勤。
綜上蕾各，我們可以得到路徑1-4-3-5
四、小結
我們可以看到庆揪，這個算法雖然時間效率不低式曲，但形式簡單、直觀缸榛。
