【圖】（六）多源最短路徑-Floyd詳解-C語(yǔ)言-創(chuàng)新互聯(lián)

圖相關(guān)文章：
1. 圖的建立 - 鄰接矩陣與鄰接表
2. 圖的遍歷 - DFS與BFS
3. 頂點(diǎn)度的計(jì)算
4. 最小生成樹(shù) - Prim與Kruskal
5. 單源最短路徑 - Dijkstra與Bellman-Ford
6. 多源最短路徑 - Floyd
7. 拓?fù)渑判駻OV網(wǎng)

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

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

Floyd算法

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

Floyd算法采用動(dòng)態(tài)規(guī)劃的思想，分為多個(gè)階段來(lái)解決問(wèn)題。

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

Floyd求解過(guò)程：

  • 首先進(jìn)行初始化，在沒(méi)有其它頂點(diǎn)中轉(zhuǎn)的情況下，求得各頂點(diǎn)間的最短路徑；

  • 在各頂點(diǎn)間增加 V 0 V_0 V0?作為中轉(zhuǎn)結(jié)點(diǎn)，求得各頂點(diǎn)間新的最短路徑；

  • 再增加 V 1 V_1 V1?作為中轉(zhuǎn)結(jié)點(diǎn)，求得各頂點(diǎn)間新的最短路徑；

    ……

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


3.1 算法思想

Floyd只能使用鄰接矩陣來(lái)實(shí)現(xiàn)。

為了方便理解，我們來(lái)手動(dòng)模擬一下實(shí)現(xiàn)過(guò)程。以有向圖演示，無(wú)向圖同理。

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

（1）初始化

在這里插入圖片描述
初始化的最短路徑矩陣其實(shí)就是鄰接矩陣，中轉(zhuǎn)頂點(diǎn)矩陣全部標(biāo)記為 ? 1 -1 ?1，代表未經(jīng)過(guò)中轉(zhuǎn)。


（2）求解

① 加入 V 0 V_0 V0?中轉(zhuǎn)

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

沒(méi)有別的頂點(diǎn)可以通過(guò) V 1 V_1 V1?中轉(zhuǎn)或使得 d i s dis dis減少，進(jìn)行下一次中轉(zhuǎn)。

在這里插入圖片描述

② 加入 V 1 V_1 V1?中轉(zhuǎn)

可以看到，當(dāng)我們添加到 V 1 V_1 V1?作為中轉(zhuǎn)時(shí)，

原先 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

沒(méi)有別的頂點(diǎn)可以通過(guò) V 1 V_1 V1?中轉(zhuǎn)或使得 d i s dis dis減少，進(jìn)行下一次中轉(zhuǎn)。

在這里插入圖片描述


③ 加入 V 2 V_2 V2?中轉(zhuǎn)

可以看到，當(dāng)我們添加到 V 2 V_2 V2?作為中轉(zhuǎn)時(shí)，

原先 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

沒(méi)有別的頂點(diǎn)可以通過(guò) V 2 V_2 V2?中轉(zhuǎn)或使得 d i s dis dis減少，進(jìn)行下一次中轉(zhuǎn)。

在這里插入圖片描述


④ 加入 V 3 V_3 V3?中轉(zhuǎn)

可以看到，當(dāng)我們添加到 V 3 V_3 V3?作為中轉(zhuǎn)時(shí)，

原先 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

沒(méi)有別的頂點(diǎn)可以通過(guò) V 3 V_3 V3?中轉(zhuǎn)或使得 d i s dis dis減少，進(jìn)行下一次中轉(zhuǎn)。

在這里插入圖片描述


⑤ 加入 V 4 V_4 V4?中轉(zhuǎn)

可以看到，當(dāng)我們添加到 V 4 V_4 V4?作為中轉(zhuǎn)時(shí)，由于 V 4 V_4 V4?的出度為0，故不會(huì)進(jìn)行更新，且已經(jīng)將所有頂點(diǎn)中轉(zhuǎn)完成，得到的便是最終結(jié)果。

在這里插入圖片描述

（3）輸出

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

而想要輸出 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?頂點(diǎn)為例：

首先 p a t h [ V 2 ] [ V 4 ] = 3 path[V_2][V_4]=3 path[V2?][V4?]=3，則說(shuō)明經(jīng)過(guò) V 3 V_3 V3?進(jìn)行中轉(zhuǎn)，路徑為 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，則說(shuō)明經(jīng)過(guò) V 1 V_1 V1?進(jìn)行中轉(zhuǎn)，路徑為 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，則說(shuō)明沒(méi)有經(jīng)過(guò)任何頂點(diǎn)進(jìn)行中轉(zhuǎn)，得到最終的路徑為 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 實(shí)現(xiàn)

給出核心部分的C語(yǔ)言代碼：

for (k = 0; k< VertexNum; k++) // 將每個(gè)頂點(diǎn)都作為中轉(zhuǎn)嘗試
{// 遍歷整個(gè)矩陣 i-行 j-列
    for (i = 0; i< VertexNum; i++)
    {for (j = 0; j< VertexNum; j++)
        {// 若經(jīng)過(guò)k頂點(diǎn)中轉(zhuǎn)，路徑更短，則更新矩陣
            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 算法分析

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

  • 時(shí)間復(fù)雜度 O ( ∣ V ∣ 3 ) O(|V|^3) O(∣V∣3)

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

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

同時(shí)Floyd也支持負(fù)權(quán)邊，也是其一個(gè)優(yōu)點(diǎn)。

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

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

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

廣告

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

成都網(wǎng)站建設(shè)公司