求圖的多源最短路的演算法

① 弗洛伊德演算法求出最短距離

（1）利用二維數組dist[i][j]記錄當前vi到vj的最短路徑長度，數組dist的初值等於圖的帶權鄰接矩陣;

（3）依次向S中加入v0,v1…vn-1，每加入一個頂點，對dist[i][j]進行一次修正：設S={v0,v1…vk-1}，加入vk，則dist(k)[i][j]=min{dist(k-1)[i][j]，dist(k-1)[i][k]+dist(k-1)[k][j]}。

dist(k)[i][j]的含義：允許中間頂點的序號最大為k時從vi到vj的最短路徑長度。
dist(n-1)[i][j]就是vi到vj的最短路徑長度。

弗洛伊德最短距離演算法（FloydShortestPathAlgorithm）又稱為插點法，是一種利用動態規劃的思想尋找給定的加權圖中多源點之間最短路徑的演算法。該演算法名稱以創始人之一、1978年圖靈獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德命名。
中文名弗洛伊德最短距離演算法
外文名FloydShortestPathAlgorithm
所屬學科IT
所屬領域程序設計
簡介
最短路問題是網路最優化中一個基本而又非常重要的問題，這一問題相對比較簡單，在實際生產和生活中經常遇到，許多的網路最優化問題可以化為最短路問題，或者用最短路演算法作為其子程序.因此，最短路的用途已遠遠超出其表面意義迄今為止，所有最短路演算法都只對不含負迴路的網路有效，實際上對含有負迴路的網路，其最短路問題是NP困難的，因此本研究所討論的網路也不含負迴路.此外，如果將無向圖每條邊用兩條端點相同、方向相反的弧來代替，可以將其化為有向圖，因而不討論無向圖.本研究中未述及的術語、記號。
Floyd演算法是一種用於尋找給定加權圖中頂點間最短路徑的演算法，以1978年圖靈獎獲得者斯坦福大學計算機科學系教授RobertW．Floyd命名。Floyd演算法採用動態規劃的原理計算兩兩頂點間最短路徑，主要解決網路路由尋找最優路徑的問題。

② 數學最短路徑問題最方便的解法是什麼

用於解決最短路徑問題的演算法被稱做「最短路徑演算法」 ，有時被簡稱作「路徑演算法」 。最常用 的路徑演算法有： Dijkstra 演算法、 A*演算法、 SPFA 演算法、 Bellman-Ford 演算法和 Floyd-Warshall 演算法， 本文主要介紹其中的三種。 最短路徑問題是圖論研究中的一個經典演算法問題，旨在尋找圖（由結點和路徑組成的）中兩 結點之間的最短路徑。 演算法具體的形式包括： 確定起點的最短路徑問題：即已知起始結點，求最短路徑的問題。 確定終點的最短路徑問題：與確定起點的問題相反，該問題是已知終結結點，求最短路徑的 問題。 在無向圖中該問題與確定起點的問題完全等同， 在有向圖中該問題等同於把所有路徑 方向反轉的確定起點的問題。 確定起點終點的最短路徑問題：即已知起點和終點，求兩結點之間的最短路徑。 全局最短路徑問題：求圖中所有的最短路徑。 Floyd 求多源、無負權邊的最短路。用矩陣記錄圖。時效性較差，時間復雜度 O(V^3)。 Floyd-Warshall 演算法（Floyd-Warshall algorithm）是解決任意兩點間的最短路徑的一種演算法， 可以正確處理有向圖或負權的最短路徑問題。 Floyd-Warshall 演算法的時間復雜度為 O(N^3)，空間復雜度為 O(N^2)。 Floyd-Warshall 的原理是動態規劃： 設 Di,j,k 為從 i 到 j 的只以(1..k)集合中的節點為中間節點的最短路徑的長度。 若最短路徑經過點 k，則 Di,j,k = Di,k,k-1 + Dk,j,k-1； 若最短路徑不經過點 k，則 Di,j,k = Di,j,k-1。 因此，Di,j,k = min(Di,k,k-1 + Dk,j,k-1 , Di,j,k-1)。 在實際演算法中，為了節約空間，可以直接在原來空間上進行迭代，這樣空間可降至二維。 Floyd-Warshall 演算法的描述如下： 1.for k ← 1 to n do 2.for i ← 1 to n do 3.for j ← 1 to n do 4.if (Di,k + Dk,j<Di,j) then 5.Di,j ← Di,k + Dk,j; 其中 Di,j 表示由點 i 到點 j 的代價，當 Di,j 為∞表示兩點之間沒有任何連接。 Dijkstra 求單源、無負權的最短路。時效性較好，時間復雜度為 O（V*V+E） 。 源點可達的話，O（V*lgV+E*lgV）=>O（E*lgV） 。 當是稀疏圖的情況時，此時 E=V*V/lgV，所以演算法的時間復雜度可為 O（V^2） 。若是斐波那 契堆作優先隊列的話，演算法時間復雜度，則為 O（V*lgV + E） 。 Bellman-Ford 求單源最短路，可以判斷有無負權迴路（若有，則不存在最短路） ，時效性較好，時間復雜 度 O（VE） 。 Bellman-Ford 演算法是求解單源最短路徑問題的一種演算法。 單源點的最短路徑問題是指：給定一個加權有向圖 G 和源點 s，對於圖 G 中的任意一點 v， 求從 s 到 v 的最短路徑。 與 Dijkstra 演算法不同的是，在 Bellman-Ford 演算法中，邊的權值可以為負數。設想從我們可以 從圖中找到一個環路（即從 v 出發，經過若干個點之後又回到 v）且這個環路中所有邊的權 值之和為負。那麼通過這個環路，環路中任意兩點的最短路徑就可以無窮小下去。如果不處 理這個負環路，程序就會永遠運行下去。而 Bellman-Ford 演算法具有分辨這種負環路的能力。 SPFA是 Bellman-Ford 的隊列優化，時效性相對好，時間復雜度 O（kE）（k<<V） 。 。 與 Bellman-ford 演算法類似， SPFA 演算法採用一系列的鬆弛操作以得到從某一個節點出發到達圖 中其它所有節點的最短路徑。所不同的是，SPFA 演算法通過維護一個隊列，使得一個節點的 當前最短路徑被更新之後沒有必要立刻去更新其他的節點， 從而大大減少了重復的操作次數。 SPFA 演算法可以用於存在負數邊權的圖，這與 dijkstra 演算法是不同的。 與 Dijkstra 演算法與 Bellman-ford 演算法都不同，SPFA 的演算法時間效率是不穩定的，即它對於不 同的圖所需要的時間有很大的差別。 在最好情形下，每一個節點都只入隊一次，則演算法實際上變為廣度優先遍歷，其時間復雜度 僅為 O(E)。另一方面，存在這樣的例子，使得每一個節點都被入隊(V-1)次，此時演算法退化為 Bellman-ford 演算法，其時間復雜度為 O(VE)。 SPFA 演算法在負邊權圖上可以完全取代 Bellman-ford 演算法， 另外在稀疏圖中也表現良好。 但是 在非負邊權圖中，為了避免最壞情況的出現，通常使用效率更加穩定的 Dijkstra 演算法，以及 它的使用堆優化的版本。通常的 SPFA 演算法在一類網格圖中的表現不盡如人意。 

③ 關於Floyd演算法，path數組一定能保存正確的路徑嗎

你說的是浙大的mooc數據結構，我也看了，她漏了path的一步初始化，即如果存在直接邊的情況下(D[i][j]<INFINITY)，是需要把path[i][j]初始化為i的。
因為如果i和j直接邊是它們的最短路徑，
if (Dist[i][k] + Dist[k][j] < Dist[i][j]) {
Dist[i][j] = Dist[i][k] + Dist[k][j];
Path[i][j] = k;
}
是不會更新path的，這樣直接邊作為最短路徑的path會為-1.