數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)記錄——圖-最短路徑問題（無權(quán)圖單源最短路徑算法、有權(quán)圖單源最短路徑算法、多源最短路徑算法、Dijkstra（迪杰斯特拉）算法、Floyd算法）

這篇具有很好參考價值的文章主要介紹了數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)記錄——圖-最短路徑問題（無權(quán)圖單源最短路徑算法、有權(quán)圖單源最短路徑算法、多源最短路徑算法、Dijkstra（迪杰斯特拉）算法、Floyd算法）。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

問題分類?

無權(quán)圖單源最短路徑算法

思路

偽代碼

時間復(fù)雜度

代碼實現(xiàn)（C語言）

有權(quán)圖單源最短路徑算法

Dijkstra（迪杰斯特拉）算法

偽代碼?

時間復(fù)雜度?

代碼實現(xiàn)（C語言）

多源最短路徑算法

兩種方法

Floyd算法

代碼實現(xiàn)（C語言）

問題分類?

最短路徑問題的抽象

在網(wǎng)絡(luò)中，求兩個不同頂點之間的所有路徑中，邊的權(quán)值之和最小的那一條路徑

這條路徑就是兩點之間的最短路徑（Shortest Path）

第一個頂點為源點（Source）

最后一個頂點為終點（Destination）

單源最短路徑問題

從某固定源點出發(fā)，求其到所有其他頂點的最短路徑。

（有向）無權(quán)圖
（有向）有權(quán)圖

多源最短路徑問題

求任意兩頂點間的最短路徑

無權(quán)圖單源最短路徑算法

思路

按照遞增的順序找出源點到各個頂點的最短路

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)記錄——圖-最短路徑問題（無權(quán)圖單源最短路徑算法、有權(quán)圖單源最短路徑算法、多源最短路徑算法、Dijkstra（迪杰斯特拉）算法、Floyd算法）

在這樣的一個圖中，先訪問與源點距離為1的頂點：

接著去訪問與源點距離為2的頂點：

最后訪問與源點距離為3的頂點，就發(fā)現(xiàn)所有頂點都已經(jīng)被訪問過了：

這樣的方式我們發(fā)現(xiàn)與BFS（廣度優(yōu)先搜索）類似，所以通過改動原本BFS的算法來實現(xiàn)。

偽代碼

?與之前學(xué)習(xí)的BFS算法不一樣的是，刪去了visited數(shù)組，不再用這個來表示頂點是否被訪問了；

而是添加了dist數(shù)組和path數(shù)組，

dist數(shù)組用于存儲從起始頂點到每個頂點的最短路徑長度。

在算法開始時，將所有頂點的初始距離設(shè)為-1（或者無窮大，一個足夠大的值）來表示尚未計算出最短路徑。

在算法執(zhí)行過程中，每當(dāng)找到一個更短的路徑時，就會更新dist數(shù)組中對應(yīng)頂點的值。

path數(shù)組用于存儲從起始頂點到每個頂點的最短路徑的前驅(qū)節(jié)點（即上一個節(jié)點）。

通過path數(shù)組，我們可以在搜索結(jié)束后從目標(biāo)頂點回溯并恢復(fù)整個最短路徑。（因為是反序所以可以利用堆棧來輸出整個最短路徑）

將頂點W的距離（即最短路徑長度）更新為頂點V的距離加1。

這意味著通過頂點V可以到達(dá)頂點W，且路徑長度比當(dāng)前已知的最短路徑長度更短。

更新頂點W的前驅(qū)節(jié)點為頂點V。這就幫助我們在找到最短路徑后回溯并恢復(fù)整個路徑。

時間復(fù)雜度

O(V + E)

其中 V 是頂點數(shù)，E 是邊數(shù)。

遍歷每個頂點：O(V)
對于每個頂點，訪問其所有鄰接頂點：O(E)

我們遍歷了每個頂點一次，并且對于每個頂點，我們只訪問了它的鄰接頂點一次。

因此，該算法的時間復(fù)雜度為 O(V + E)。

注意：這個時間復(fù)雜度假設(shè)圖的表示方式為鄰接表，其中訪問每個頂點的鄰接頂點的時間復(fù)雜度為 O(1)。如果使用鄰接矩陣表示圖，那么訪問每個頂點的鄰接頂點的時間復(fù)雜度將變?yōu)?O(V)，總的時間復(fù)雜度將變?yōu)?O(V^2)。

代碼實現(xiàn)（C語言）

/* 
   鄰接表存儲 - 無權(quán)圖的單源最短路算法
   輸入：圖Graph，距離數(shù)組dist[]，路徑數(shù)組path[]，源點S
   輸出：dist[]中記錄了源點S到各頂點的最短距離，path[]中記錄了最短路徑的前驅(qū)頂點
   dist[]和path[]全部初始化為-1
*/

void Unweighted(LGraph Graph, int dist[], int path[], Vertex S)
{
    Queue Q;  // 定義隊列Q，用于廣度優(yōu)先搜索
    Vertex V;  // 當(dāng)前頂點V
    PtrToAdjVNode W;  // 指向當(dāng)前頂點V的鄰接點的指針W
    
    Q = CreateQueue(Graph->Nv);  // 創(chuàng)建空隊列Q，最大容量為圖的頂點數(shù)Nv
    dist[S] = 0;  // 初始化源點S的距離為0
    AddQ(Q, S);  // 將源點S入隊

    while (!IsEmpty(Q))
    {
        V = DeleteQ(Q);  // 從隊列Q中刪除一個頂點V，作為當(dāng)前頂點
        for (W = Graph->G[V].FirstEdge; W; W = W->Next)
        {
            /* 對V的每個鄰接點W->AdjV */
            if (dist[W->AdjV] == -1)
            {
                /* 若W->AdjV未被訪問過 */
                dist[W->AdjV] = dist[V] + 1;  // 更新W->AdjV到源點S的距離
                path[W->AdjV] = V;  // 將當(dāng)前頂點V記錄在S到W->AdjV的路徑上
                AddQ(Q, W->AdjV);  // 將W->AdjV入隊，繼續(xù)廣度優(yōu)先搜索
            }
        }
    } /* while結(jié)束*/
}

有權(quán)圖單源最短路徑算法

Dijkstra（迪杰斯特拉）算法

令S = {源點s + 已經(jīng)確定了最短路徑的頂點}
對任一未收錄的頂點v，定義dist[v]為s到v的最短路徑長度，但該路徑僅經(jīng)過S中的頂點。即路徑的最小長度
該路徑是按照遞增的順序生成的，則

1.真正的最短路必須只經(jīng)過S中的頂點。

2.每次從未收錄的頂點中選一個dist最小的收錄（貪心算法）。

3.增加一個v進(jìn)入S，可能影響另外一個w的dist值

對于第1點：

在算法的每一步，我們將一個頂點加入集合S，該頂點是在當(dāng)前階段中距離源點s的最短路徑長度最小的頂點。由于我們每次只選擇當(dāng)前最短路徑的頂點，所以可以確保這些頂點經(jīng)過的路徑是當(dāng)前階段中最短的路徑。

對于第3點：

如果收錄v使得s到w的路徑變短，則s到w的路徑一定經(jīng)過v，并且v到w有一條邊。

在每一步中，選擇的頂點v是當(dāng)前階段中距離源點s最近的頂點，而且該距離是經(jīng)過已確定最短路徑頂點集合S的路徑長度。

當(dāng)將頂點v加入集合S后，我們更新其他頂點的dist值，以反映新的最短路徑長度。如果從v到w之間不存在直接的邊，那么根據(jù)Dijkstra算法的貪心策略，頂點w將不會被更新為新的最短路徑。

所以是一定存在一條從v到頂點w的邊，并且通過v的路徑長度加上邊的權(quán)重小于w當(dāng)前的dist值，那么說明我們可以通過頂點v找到一條更短的路徑來達(dá)到頂點w。因此，為了保證選擇的是下一個最近的頂點，我們要先進(jìn)行比較。即當(dāng)前的dist值與通過v的路徑長度加上邊的權(quán)重比較。

$數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)記錄——圖-最短路徑問題（無權(quán)圖單源最短路徑算法、有權(quán)圖單源最短路徑算法、多源最短路徑算法、Dijkstra（迪杰斯特拉）算法、Floyd算法）$

偽代碼?

E<V,W>表示V到W的邊上的權(quán)重。

時間復(fù)雜度?

鄰接矩陣表示法

在使用鄰接矩陣表示圖的情況下，每次查找未收錄頂點中dist最小者的時間復(fù)雜度為O(V)，并且需要進(jìn)行V次這樣的查找。

在每次查找中，還需要遍歷當(dāng)前頂點的所有鄰接頂點，即總共需要進(jìn)行V次遍歷。

因此，總的時間復(fù)雜度為O(V^2 + E)。

鄰接表表示法

而在使用鄰接表表示圖的情況下，可以使用最小堆來查找未收錄頂點中dist最小者，可以將時間復(fù)雜度降低到O(logV)。

在每次查找中，僅需遍歷當(dāng)前頂點的鄰接表，即遍歷的次數(shù)不會超過圖中的邊數(shù)E。因此，總的時間復(fù)雜度為O((V + E)logV)。

注意：在稀疏圖（邊的數(shù)量相對較少）的情況下，鄰接表表示圖的效率更高。而在稠密圖（邊的數(shù)量接近頂點數(shù)量的平方）的情況下，鄰接矩陣表示圖的效率更高。

代碼實現(xiàn)（C語言）

/* 
   鄰接矩陣存儲 - 有權(quán)圖的單源最短路算法
   輸入：圖Graph，距離數(shù)組dist[]，路徑數(shù)組path[]，源點S
   輸出：dist[]中記錄了源點S到各頂點的最短距離，path[]中記錄了最短路徑的前驅(qū)頂點
   使用鄰接矩陣表示圖，INFINITY表示不存在的邊
*/

Vertex FindMinDist(MGraph Graph, int dist[], int collected[])
{ 
    /* 返回未被收錄頂點中dist最小者 */
    Vertex MinV, V;
    int MinDist = INFINITY;

    for (V = 0; V < Graph->Nv; V++)
    {
        if (collected[V] == false && dist[V] < MinDist)
        {
            /* 若V未被收錄，且dist[V]更小 */
            MinDist = dist[V]; /* 更新最小距離 */
            MinV = V; /* 更新對應(yīng)頂點 */
        }
    }
    if (MinDist < INFINITY) /* 若找到最小dist */
        return MinV; /* 返回對應(yīng)的頂點下標(biāo) */
    else
        return ERROR;  /* 若這樣的頂點不存在，返回錯誤標(biāo)記 */
}

bool Dijkstra(MGraph Graph, int dist[], int path[], Vertex S)
{
    int collected[MaxVertexNum];
    Vertex V, W;

    /* 初始化：此處默認(rèn)鄰接矩陣中不存在的邊用INFINITY表示 */
    for (V = 0; V < Graph->Nv; V++)
    {
        dist[V] = Graph->G[S][V];
        if (dist[V] < INFINITY)
            path[V] = S;
        else
            path[V] = -1;
        collected[V] = false;
    }
    /* 先將起點收入集合 */
    dist[S] = 0;
    collected[S] = true;

    while (1)
    {
        /* V = 未被收錄頂點中dist最小者 */
        V = FindMinDist(Graph, dist, collected);
        if (V == ERROR) /* 若這樣的V不存在 */
            break;      /* 算法結(jié)束 */
        collected[V] = true;  /* 收錄V */
        for (W = 0; W < Graph->Nv; W++) /* 對圖中的每個頂點W */
        {
            /* 若W是V的鄰接點并且未被收錄 */
            if (collected[W] == false && Graph->G[V][W] < INFINITY)
            {
                if (Graph->G[V][W] < 0) /* 若有負(fù)邊 */
                    return false; /* 不能正確解決，返回錯誤標(biāo)記 */
                /* 若收錄V使得dist[W]變小 */
                if (dist[V] + Graph->G[V][W] < dist[W])
                {
                    dist[W] = dist[V] + Graph->G[V][W]; /* 更新dist[W] */
                    path[W] = V; /* 更新S到W的路徑 */
                }
            }
        }
    } /* while結(jié)束*/
    return true; /* 算法執(zhí)行完畢，返回正確標(biāo)記 */
}

多源最短路徑算法

兩種方法

方法1：直接將單元最短路算法調(diào)用V遍

在稀疏圖的情況下，單源最短路徑算法時間復(fù)雜度為O（V^2 + E）;

現(xiàn)在是多源，要調(diào)用V遍，故而時間復(fù)雜度T為：O（V^3 + E*V）

方法2：Floyd算法

這個算法用于稠密圖，時間復(fù)雜度T直接就為：O（V^3）

在下面進(jìn)行解釋：

Floyd算法

對于稠密圖的話，我們通常是可以使用鄰接矩陣來表示圖的，F(xiàn)loyd算法也是基于鄰接矩陣的一個算法。

?= 路徑的最小長度
,即給出了i到j(luò)的真正最短距離
,即初始的矩陣定義為：帶權(quán)的鄰接矩陣，對角元為0.表示結(jié)點到自身的距離為0
當(dāng)已經(jīng)完成，遞推到時：

最短路徑時，?=?。

最短路徑時，該路徑必定由兩段最短路徑組成： $數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)記錄——圖-最短路徑問題（無權(quán)圖單源最短路徑算法、有權(quán)圖單源最短路徑算法、多源最短路徑算法、Dijkstra（迪杰斯特拉）算法、Floyd算法）$

Floyd算法也是逐步地求出最短距離的，通過遍歷所有可能的中間節(jié)點k，并不斷嘗試更新D[i][j]的值，F(xiàn)loyd算法逐步優(yōu)化路徑長度，最終找到圖中所有節(jié)點對之間的最短路徑。

假設(shè)我們有一個圖，其中有節(jié)點i和節(jié)點j需要連接，并且我們已經(jīng)知道了節(jié)點i到節(jié)點j的當(dāng)前最短路徑長度（存儲在D[i][j]中）。

現(xiàn)在，我們引入一個中間節(jié)點k，想要通過節(jié)點k來嘗試找到更短的路徑，即嘗試在節(jié)點i和節(jié)點j之間建立一條路徑，其中包括節(jié)點k。

我們首先考慮從節(jié)點i到節(jié)點k的路徑長度，這個距離我們可以在D數(shù)組中找到，即D[i][k]。接著，我們考慮從節(jié)點k到節(jié)點j的路徑長度，同樣可以在D數(shù)組中找到，即D[k][j]。

現(xiàn)在，我們將這兩段路徑長度加在一起，得到D[i][k] + D[k][j]。這個值表示通過節(jié)點k連接的從節(jié)點i到節(jié)點j的路徑長度。

接下來，我們將這個通過節(jié)點k的路徑長度與當(dāng)前已知的最短路徑長度（即D[i][j]）進(jìn)行比較。

如果通過節(jié)點k的路徑長度更短，那么我們更新D[i][j]的值為D[i][k] + D[k][j]，表示我們找到了一條經(jīng)過節(jié)點k的更短路徑。
如果通過節(jié)點k的路徑長度并不比當(dāng)前已知的最短路徑長度更短，那么我們不做任何更改，保持D[i][j]不變。

代碼實現(xiàn)（C語言）

/* 鄰接矩陣存儲 - 多源最短路算法 */

bool Floyd(MGraph Graph, WeightType D[][MaxVertexNum], Vertex path[][MaxVertexNum]) 
{
    Vertex i, j, k;

    /* 初始化 */
    for (i = 0; i < Graph->Nv; i++)
    {
        for (j = 0; j < Graph->Nv; j++) 
        {
            D[i][j] = Graph->G[i][j];  // 初始化最短路徑數(shù)組D為圖的鄰接矩陣
            path[i][j] = -1;           // 初始化路徑數(shù)組path為-1，表示當(dāng)前節(jié)點間沒有中間節(jié)點
        }
    }

    for (k = 0; k < Graph->Nv; k++) 
    {
        for (i = 0; i < Graph->Nv; i++) 
        {
            for (j = 0; j < Graph->Nv; j++) 
            {
                if (D[i][k] + D[k][j] < D[i][j]) 
                {  // 如果通過中間節(jié)點k可以獲得更短的路徑
                    D[i][j] = D[i][k] + D[k][j];    // 更新節(jié)點i到節(jié)點j的最短路徑長度
                    if (i == j && D[i][j] < 0) 
                    {    // 若發(fā)現(xiàn)負(fù)值圈，即存在權(quán)重之和為負(fù)的回路
                        return false;               // 不能正確解決，返回錯誤標(biāo)記
                    }
                    path[i][j] = k;                  // 更新節(jié)點i到節(jié)點j的路徑經(jīng)過的中間節(jié)點為k
                }
            }
        }
    }
    return true;  // 算法執(zhí)行完畢，返回正確標(biāo)記
}

end

學(xué)習(xí)自：MOOC數(shù)據(jù)結(jié)構(gòu)——陳越、何欽銘文章來源地址http://www.zghlxwxcb.cn/news/detail-480410.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)記錄——圖-最短路徑問題（無權(quán)圖單源最短路徑算法、有權(quán)圖單源最短路徑算法、多源最短路徑算法、Dijkstra（迪杰斯特拉）算法、Floyd算法）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！