圖相關文章：
1. 圖的建立 - 鄰接矩陣與鄰接表
2. 圖的遍歷 - DFS與BFS
3. 頂點度的計算
4. 最小生成樹 - Prim與Kruskal
5. 單源最短路徑 - Dijkstra與Bellman-Ford
6. 多源最短路徑 - Floyd
7. 拓撲排序AOV網(wǎng)

創(chuàng)新互聯(lián)專業(yè)為企業(yè)提供常寧網(wǎng)站建設、常寧做網(wǎng)站、常寧網(wǎng)站設計、常寧網(wǎng)站制作等企業(yè)網(wǎng)站建設、網(wǎng)頁設計與制作、常寧企業(yè)網(wǎng)站模板建站服務，10多年常寧做網(wǎng)站經驗，不只是建網(wǎng)站，更提供有價值的思路和整體網(wǎng)絡服務。

---

文章目錄

• Floyd算法
• • 3.1 算法思想
  • • （1）初始化
    • （2）求解
    • （3）輸出
  • 3.2 實現(xiàn)
  • 3.3 算法分析

---

Floyd算法

Floyd算法是求解多源最短路徑問題的典型算法，可以知道圖中任意兩點之間的最短路徑。該算法對于有向圖、無向圖都適用，同時允許圖中帶有負權邊，但是不允許有負權環(huán)。

Floyd算法采用動態(tài)規(guī)劃的思想，分為多個階段來解決問題。

若圖 G G G有 n n n個頂點 ( V 0 ～ V n ? 1 ) (V_0 \sim V_{n-1}) (V0?～Vn?1?)，則將求圖中每一對頂點之間的最短路徑分 n n n個階段∶

Floyd求解過程：

• 首先進行初始化，在沒有其它頂點中轉的情況下，求得各頂點間的最短路徑；

• 在各頂點間增加 V 0 V_0 V0?作為中轉結點，求得各頂點間新的最短路徑；

• 再增加 V 1 V_1 V1?作為中轉結點，求得各頂點間新的最短路徑；

  ……

• 最后增加 V n ? 1 V_{n-1} Vn?1?作為中轉結點，求得各頂點間最終的最短路徑。

---

3.1 算法思想

Floyd只能使用鄰接矩陣來實現(xiàn)。

為了方便理解，我們來手動模擬一下實現(xiàn)過程。以有向圖演示，無向圖同理。

我們使用兩個大小為 n × n n \times n n×n的二維數(shù)組分別記錄最短路徑 d i s dis dis與中轉頂點 p a t h path path。其中，最短路徑矩陣可以告訴我們任意兩頂點間的最短距離；而中轉頂點矩陣可以告訴我們路徑。

（1）初始化

初始化的最短路徑矩陣其實就是鄰接矩陣，中轉頂點矩陣全部標記為 ? 1 -1 ?1，代表未經過中轉。

（2）求解

① 加入 V 0 V_0 V0?中轉

可以看到， V 0 V_0 V0?頂點的入度為0，所以任何頂點都不能到達 V 0 V_0 V0?，最短路徑與中轉頂點矩陣不變。

沒有別的頂點可以通過 V 1 V_1 V1?中轉或使得 d i s dis dis減少，進行下一次中轉。

② 加入 V 1 V_1 V1?中轉

可以看到，當我們添加到 V 1 V_1 V1?作為中轉時，

原先 V 2 → V 3 = ∞ V_2 \rightarrow V_3 = \infty V2?→V3?=∞，現(xiàn)在 V 2 → V 1 → V 3 = 2 V_2 \rightarrow V_1 \rightarrow V_3= 2 V2?→V1?→V3?=2，更新 d i s [ V 2 ] [ V 3 ] = 2 dis[V_2][V_3]=2 dis[V2?][V3?]=2， p a t h [ V 2 ] [ V 3 ] = 1 path[V_2][V_3]=1 path[V2?][V3?]=1

原先 V 2 → V 4 = 7 V_2 \rightarrow V_4 = 7 V2?→V4?=7，現(xiàn)在 V 2 → V 1 → V 4 = 6 V_2 \rightarrow V_1 \rightarrow V_4= 6 V2?→V1?→V4?=6，更新 d i s [ V 2 ] [ V 4 ] = 6 dis[V_2][V_4]=6 dis[V2?][V4?]=6， p a t h [ V 2 ] [ V 4 ] = 1 path[V_2][V_4]=1 path[V2?][V4?]=1

沒有別的頂點可以通過 V 1 V_1 V1?中轉或使得 d i s dis dis減少，進行下一次中轉。

③ 加入 V 2 V_2 V2?中轉

可以看到，當我們添加到 V 2 V_2 V2?作為中轉時，

原先 d i s [ V 0 ] [ V 1 ] = ∞ dis[V_0][V_1] = \infty dis[V0?][V1?]=∞，現(xiàn)在 d i s [ V 0 ] [ V 2 ] + d i s [ V 2 ] [ V 1 ] = 2 dis[V_0][V_2] + dis[V_2][V_1]= 2 dis[V0?][V2?]+dis[V2?][V1?]=2，更新 d i s [ V 0 ] [ V 1 ] = 2 dis[V_0][V_1]=2 dis[V0?][V1?]=2， p a t h [ V 0 ] [ V 1 ] = 2 path[V_0][V_1]=2 path[V0?][V1?]=2

原先 d i s [ V 0 ] [ V 3 ] = ∞ dis[V_0][V_3] = \infty dis[V0?][V3?]=∞，現(xiàn)在 d i s [ V 0 ] [ V 2 ] + d i s [ V 2 ] [ V 3 ] = 3 dis[V_0][V_2] + dis[V_2][V_3]= 3 dis[V0?][V2?]+dis[V2?][V3?]=3，更新 d i s [ V 0 ] [ V 3 ] = 3 dis[V_0][V_3]=3 dis[V0?][V3?]=3， p a t h [ V 0 ] [ V 3 ] = 2 path[V_0][V_3]=2 path[V0?][V3?]=2

原先 d i s [ V 0 ] [ V 4 ] = 10 dis[V_0][V_4] = 10 dis[V0?][V4?]=10，現(xiàn)在 d i s [ V 0 ] [ V 2 ] + d i s [ V 2 ] [ V 4 ] = 7 dis[V_0][V_2] + dis[V_2][V_4]= 7 dis[V0?][V2?]+dis[V2?][V4?]=7，更新 d i s [ V 0 ] [ V 4 ] = 7 dis[V_0][V_4]=7 dis[V0?][V4?]=7， p a t h [ V 0 ] [ V 4 ] = 2 path[V_0][V_4]=2 path[V0?][V4?]=2

沒有別的頂點可以通過 V 2 V_2 V2?中轉或使得 d i s dis dis減少，進行下一次中轉。

④ 加入 V 3 V_3 V3?中轉

可以看到，當我們添加到 V 3 V_3 V3?作為中轉時，

原先 d i s [ V 0 ] [ V 4 ] = 7 dis[V_0][V_4] = 7 dis[V0?][V4?]=7，現(xiàn)在 d i s [ V 0 ] [ V 3 ] + d i s [ V 3 ] [ V 4 ] = 4 dis[V_0][V_3] + dis[V_3][V_4]= 4 dis[V0?][V3?]+dis[V3?][V4?]=4，更新 d i s [ V 0 ] [ V 4 ] = 4 dis[V_0][V_4]= 4 dis[V0?][V4?]=4， p a t h [ V 0 ] [ V 4 ] = 3 path[V_0][V_4]=3 path[V0?][V4?]=3

原先 d i s [ V 1 ] [ V 4 ] = 5 dis[V_1][V_4] = 5 dis[V1?][V4?]=5，現(xiàn)在 d i s [ V 1 ] [ V 3 ] + d i s [ V 3 ] [ V 4 ] = 2 dis[V_1][V_3] + dis[V_3][V_4]= 2 dis[V1?][V3?]+dis[V3?][V4?]=2，更新 d i s [ V 1 ] [ V 4 ] = 2 dis[V_1][V_4]=2 dis[V1?][V4?]=2， p a t h [ V 1 ] [ V 4 ] = 3 path[V_1][V_4]=3 path[V1?][V4?]=3

原先 d i s [ V 2 ] [ V 4 ] = 6 dis[V_2][V_4] = 6 dis[V2?][V4?]=6，現(xiàn)在 d i s [ V 2 ] [ V 3 ] + d i s [ V 3 ] [ V 4 ] = 3 dis[V_2][V_3] + dis[V_3][V_4]= 3 dis[V2?][V3?]+dis[V3?][V4?]=3，更新 d i s [ V 2 ] [ V 4 ] = 3 dis[V_2][V_4]=3 dis[V2?][V4?]=3， p a t h [ V 1 ] [ V 4 ] = 3 path[V_1][V_4]=3 path[V1?][V4?]=3

沒有別的頂點可以通過 V 3 V_3 V3?中轉或使得 d i s dis dis減少，進行下一次中轉。

⑤ 加入 V 4 V_4 V4?中轉

可以看到，當我們添加到 V 4 V_4 V4?作為中轉時，由于 V 4 V_4 V4?的出度為0，故不會進行更新，且已經將所有頂點中轉完成，得到的便是最終結果。

（3）輸出

d i s [ i ] [ j ] dis[i][j] dis[i][j]存儲的便是 V i ～ V j V_i \sim V_j Vi?～Vj?的最短路徑長度。

而想要輸出 V i ～ V j V_i \sim V_j Vi?～Vj?的最短路徑，則需要順著 p a t h path path數(shù)組往前找。

以上圖的 V 2 ～ V 4 V_2 \sim V_4 V2?～V4?頂點為例：

首先 p a t h [ V 2 ] [ V 4 ] = 3 path[V_2][V_4]=3 path[V2?][V4?]=3，則說明經過 V 3 V_3 V3?進行中轉，路徑為 V 2 → ( V 3 ) → V 4 V_2 \rightarrow (V_3) \rightarrow V_4 V2?→(V3?)→V4?

接著找 p a t h [ V 2 ] [ V 3 ] = 1 path[V_2][V_3]=1 path[V2?][V3?]=1，則說明經過 V 1 V_1 V1?進行中轉，路徑為 V 2 → ( V 1 ) → V 3 → V 4 V_2 \rightarrow (V_1) \rightarrow V_3 \rightarrow V_4 V2?→(V1?)→V3?→V4?

接著找 p a t h [ V 2 ] [ V 1 ] = ? 1 path[V_2][V_1]=-1 path[V2?][V1?]=?1，則說明沒有經過任何頂點進行中轉，得到最終的路徑為 V 2 → V 1 → V 3 → V 4 V_2 \rightarrow V_1 \rightarrow V_3 \rightarrow V_4 V2?→V1?→V3?→V4?

---

3.2 實現(xiàn)

給出核心部分的C語言代碼：

for (k = 0; k< VertexNum; k++) // 將每個頂點都作為中轉嘗試
{// 遍歷整個矩陣 i-行 j-列
    for (i = 0; i< VertexNum; i++)
    {for (j = 0; j< VertexNum; j++)
        {// 若經過k頂點中轉，路徑更短，則更新矩陣
            if (dis[i][k] + dis[k][j]< dis[i][j])
            {dis[i][j] = dis[i][k] + dis[k][j]; // 更新dis矩陣
                path[i][j] = k;                    // 更新path矩陣
            }
        }
    }
}

---

3.3 算法分析

• 空間復雜度 O ( ∣ V ∣ 2 ) O(|V|^2) O(∣V∣2)

• 時間復雜度 O ( ∣ V ∣ 3 ) O(|V|^3) O(∣V∣3)

估計這時候你也看出了一些問題，我使用Dijkstra算法將每個頂點作為起點計算一遍，時間復雜度不也是 O ( ∣ V ∣ 3 ) O(|V|^3) O(∣V∣3)嗎？那Floyd算法的優(yōu)勢在哪里呢？

其實，雖然兩種算法都是 O ( ∣ V ∣ 3 ) O(|V|^3) O(∣V∣3)，但是前面的系數(shù)并不相同，F(xiàn)loyd的系數(shù)會更小一些，所有效率也會更高一些。也因此，即使它的復雜度到達了 O ( ∣ V ∣ 3 ) O(|V|^3) O(∣V∣3)的程度，對于一些中小規(guī)模的圖仍然是適用的。

同時Floyd也支持負權邊，也是其一個優(yōu)點。

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

文章題目：【圖】（六）多源最短路徑-Floyd詳解-C語言-創(chuàng)新互聯(lián)
當前地址：http://aaarwkj.com/article42/dshjhc.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供搜索引擎優(yōu)化、做網(wǎng)站、網(wǎng)頁設計公司、品牌網(wǎng)站建設、品牌網(wǎng)站設計、電子商務

廣告

聲明：本網(wǎng)站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)