第六章 最短路徑

Floyd-Warshall

多源最短路徑問題：求任意兩點之間的最短路徑。

可以通過深度和廣度優先搜索求出兩點之間的最短路徑：進行n^2遍深度或廣度優先搜索，即對每兩個點都進行一次深度或廣度優先搜索，便可以求得任意兩點之間的最短路徑。

如果要讓任意兩點（例如a->b）之間的路程變短，只能引入第三個點（例如k），並通過這個頂點k中轉即a->k->b，才可能縮短原來從a到b的路程。

甚至有時候不只通過一個點，而是經過兩個點或者更多點中轉會更短。

每個頂點都有可能使得另外兩個頂點之間的路程變短。

當任意兩點之間不允許經過第三個點時，這些點之間的最短路程就是初始路程。

假如現在只允許經過1號頂點中轉，求任意兩點的最短路程。只需判斷e[i][1]+e[1][j]是否比e[i][j]要小即可。其中，e[i][j]表示從i到j頂點之間的路程，e[i][1]+e[1][j]表示的是從i先到1，再從1到j的路程之和。

for(i = 1; i <= n; ++i)
    for(j = 1; j <= n; ++j)
        if(e[i][j] > e[i][1] + e[1][j])
            e[i][j] = e[i][1] + e[1][j];

接下來只允許經過1和2兩個頂點的情況下任意兩點之間的最短路程。只需在只允許經過1時任意兩點的最短路徑的結果下，再判斷如果經過2是否可以使得i到j之間的路程變得更短，即判斷e[i][2]+e[2][j]是否比e[i][j]更短？

//經過1
for(i = 1; i <= n; ++i)
    for(j = 1; j <= n; ++j)
        if(e[i][j] > e[i][1] + e[1][j])
            e[i][j] = e[i][1] + e[1][j];

//經過2
for(i = 1; i <= n; ++i)
    for(j = 1; j <= n; ++j)
        if(e[i][j] > e[i][2] + e[2][j])
            e[i][j] = e[i][2] + e[2][j];

綜上所述，基本思想為：最開始只允許經過1進行中轉，接下來只允許經過1和2進行中轉……允許經過1~n號所有頂點進行中轉，求任意兩點之間的最短路程。這是一種“動態規劃”思想，從i到j只經過前k號點的最短路程。

for(k = 1; k <= n; ++k)
    for(i = 1; i <= n; ++i)
        for(j = 1; j <= n; ++j)
            if(e[i][j] > e[i][k] + e[k][j])
                e[i][j] = e[i][k] + e[k][j];

示例

#include
#include
#include
#include

using namespace std;

int main(void)
{
    int v = 4;  //頂點數
    int e = 8;  //邊數

    vector> graph(v, vector(v, INT_MAX));
    for (int i = 0; i < v; ++i)
        graph[i][i] = 0;
    graph[0][1] = 2;
    graph[0][2] = 6;
    graph[0][3] = 4;
    graph[1][2] = 3;
    graph[2][0] = 7;
    graph[2][3] = 1;
    graph[3][0] = 5;
    graph[3][2] = 12;
    /*
    0  2  6  4
    ∞ 0  3  ∞
    7  ∞ 0  1
    5  ∞ 12 0
    */
    //1~k作為中轉點
    for (int k = 0; k < v; ++k)
    {
        for (int i = 0; i < v; ++i)
        {
            for (int j = 0; j < v; ++j)
            {
                if (graph[i][k] < INT_MAX && graph[k][j] < INT_MAX
                    && graph[i][j] > graph[i][k] + graph[k][j])  //防止相加溢出
                    graph[i][j] = graph[i][k] + graph[k][j];
            }
        }
    }

    for (const auto & line : graph)
    {
        for (const auto & point : line)
            cout << setw(3) << point;
        cout << endl;
    }

    return 0;
}

通過Floyd-Warshall算法可以求出任意兩個點之間的最短路徑，時間復雜度為O(N^3)。由於Floyd-Warshall算法實現起來非常容易，所以如果時間復雜度要求不高，使用Floyd-Warshall來指定兩點之間的最短路徑或者指定一個點到其余各個頂點的最短路徑也是可行的。

Floyd-Warshall算法不能解決帶有“負權回路”（負權環）的圖，因為帶有“負權回路”的圖沒有最短路徑。

如果一個圖中帶有“負權回路”，那麼這個圖則沒有最短路徑。

Floyd-Warshall算法由Robert W.Floyd於1962年發表在Communications of the ACM上。同年Stephen Warshall也獨立發表了這個算法。Robert W.Floyd還和J.W.J.Williams於1964年共同發明了著名的堆排序算法，他在1978年獲得了圖靈獎。

Dijkstra算法——通過邊松弛實現

單源最短路徑：求一個點（源點）到其余各個點的最短路徑。

Dijkstra算法主要思想：通過“邊”松弛源點到其余各個頂點的路程。

每次找到離源點最近的一個頂點，然後以該頂點為中心進行擴展，最終得到源點到其余所有點的最短路徑。

將所有的頂點分為兩部分：已知最短路程的頂點集合P和未知最短路徑的頂點集合Q。最開始，已知最短路徑的頂點集合P中只有源點一個頂點。 設置源點s到自己的最短路徑為0。若存在有源點能直接到達的頂點i，則把dis[i]設為e[s][i]。同時把所有其他（源點不能直接到達的）頂點的最短路徑設為∞。 在集合Q的所有頂點中選擇一個離源點s最近的頂點u（即dis[u]最小）加入到集合P。考察所有以點u為起點的邊，對每一條邊進行松弛操作——例如存在一條從u到v的邊，那麼可以通過將邊u->v添加到尾部來拓展一條從s到v的路徑，這條路徑的長度是dis[u]+e[u][v]。如果這個值比目前已知的dis[v]要小，可以用新值來替代當前dis[v]中的值。 重復第3步，如果集合Q為空，算法結束。最終dis數組中的值就是源點到所有頂點的最短路徑。

#include
#include
#include

using namespace std;

int main(void)
{
    int v = 6;  //頂點數
    int e = 9;  //邊數

    vector> graph(v, vector(v, INT_MAX));
    vector flags(v, false);
    for (int i = 0; i < v; ++i)
        graph[i][i] = 0;
    graph[0][1] = 1;
    graph[0][2] = 12;
    graph[1][2] = 9;
    graph[1][3] = 3;
    graph[2][4] = 5;
    graph[3][2] = 4;
    graph[3][4] = 13;
    graph[3][5] = 15;
    graph[4][5] = 4;
    /*
    0  2  6  4
    ∞ 0  3  ∞
    7  ∞ 0  1
    5  ∞ 12 0
    */

    vector dis(v);
    //以0為源點，初始化
    for (int i = 0; i < v; ++i)
        dis[i] = graph[0][i];
    flags[0] = true;

    //Dijkstra
    for (int i = 1; i < v; ++i)  //只需v-1次循環
    {
        //找到目前離源點最近的未標記的點
        int min_dis = INT_MAX;  //記錄最小
        int v_index;  //最近是哪個點
        for (int j = 0; j < v; ++j)
        {
            if (flags[j] == false && dis[j] < min_dis)
            {
                min_dis = dis[j];
                v_index = j;
            }
        }
        flags[v_index] = true;  //標記這個最近的點為確定

        //以找到的點所關聯的邊來進行松弛操作
        for (int j = 0; j < graph[v_index].size(); ++j)
        {
            if (graph[v_index][j] < INT_MAX)
            {
                //這條邊是存在的
                if (dis[j] > dis[v_index] + graph[v_index][j])
                    dis[j] = dis[v_index] + graph[v_index][j];
            }
        }
    }

    //單源最短路徑結果
    for (const auto & i : dis)
        cout << i << ' ';
    cout << endl;

    return 0;
}

上述實現的算法時間復雜度為O(N^2)，每次找到離源點最近的點的時間復雜度為O(N)，可以用堆進行優化，使得O(N)降低為O(logN)。

邊數M遠少於N^2的圖稱為稀疏圖，而相對較大的圖稱為稠密圖，對於稀疏圖可以用鄰接表來代替鄰接矩陣，使得整個時間復雜度優化到O((M+N)logN)。

在最壞情況下M就是N^2，這樣(M+N)logN比N^2還大，但是大多數情況下並不會有那麼多邊，所以通常(M+N)logN要比N^2小很多。

求最短路徑的Dijkstra算法是一種基於貪心策略的算法。每次新擴展一個路程最短的點，更新與其相鄰的點的路程。當所有邊權都為正時，由於不會存在一個路程更短的沒擴展過的點，所以這個點的路程永遠不會再被改變，因而保證了算法的正確性。不過根據這個原理，用Dijkstra算法求最短路徑的圖是不能有負權邊的，因為擴展到負權邊的時候會產生更短的路程，有可能破壞了已經更新的點路程不會改變的性質。

Dijkstra算法由荷蘭計算機科學家Edsger Wybe Dijkstra於1959年提出，發表在Numerische Mathematik的創刊號上，但1956年他就發現了這個算法。

Bellman-Ford——解決負權邊

Dijkstra算法雖然好，但是它不能解決帶有負權邊的圖。

Bellman-Ford算法非常簡單，並且可以完美地解決帶有負權邊的圖。

//核心代碼
for(k = 1; k <= n - 1; ++k)
    for(i = 1; i <= m; ++i)
        if(dis[v[i]] > dis[u[i]] + w[i])
            dis[v[i]] = dis[u[i]] + w[i];

上面代碼中，外循環一共循環了n-1次（n為頂點的個數），內循環循環了m次（m為邊的個數），即枚舉每一條邊。

dis數組的作用與Dijkstra算法一樣，用來記錄源點到其余各個頂點的最短路徑。

u、v和w三個數組用來記錄邊的信息，對於第i條邊，從頂點u[i]到頂點v[i]這條邊的權值為w[i]。

if語句的意思是，看能夠通過u[i]->v[i]（權值w[i]）這條邊，使得源點到v[i]的距離變短。即源點到u[i]的距離（dis[u[i]]）加上u[i]->v[i]這條邊的值w[i]是否會比原來源點到v[i]的距離（dis[v[i]]）要小。這一點跟Dijkstra算法的松弛操作是一樣的。

第一輪在對所有的邊進行松弛之後，得到的是從源點“只能經過一條邊”到達其余各頂點的最短路徑長度。第二輪在對所有的邊進行松弛之後，得到的是從源點“最多經過兩條邊”到達其余各頂點的最短路徑長度。如果進行k輪的話，得到的就是源點“最多經過k條邊”到達其余各頂點的最短路徑長度。

那需要進行多少輪？

只需要進行n-1輪就可以，因為在一個含有n個頂點的圖中，任意兩點之間的最短路徑最多包含n-1條邊。

n-1？最短路徑中不可能包含回路嗎？

不可能！最短路徑肯定是一個不包含回路的簡單路徑。回路分為正權回路（回路權值之和為正）和負權回路（回路權值之和為負）。

如果最短路徑中包含正權回路，那麼去掉這個回路，一定可以得到更短的路徑。

如果最短路徑中包含負權回路，那麼肯定沒有最短路徑，因為每多走一次負權回路就可以得到更短的路勁。

因此，最短路徑肯定是一個不包含回路的簡單路徑，即最多包含n-1條邊，所以進行n-1此松弛就可以了。

因為最短路徑上“最多”有n-1條邊，因此Bellman-Ford算法“最多”有n-1個階段。（可能n-1個階段之前就已經穩定了）

在每一個階段，對每一條邊都要執行松弛操作。每實施一次松弛操作，就會有一些頂點已經求得最短路徑，即這些頂點的最短路徑的“估計值”變為“確定值”。此後這些頂點的最短路徑的值就會一直保持不變，不再受後續松弛操作的影響（由於後面每個階段還是會判斷是否需要松弛，所以要進行優化）。在前k個階段結束後，就已經找出了從源點發出“最多經過k條邊”到達各個頂點的最短路徑。直到進行完n-1個階段後，便得出了最多經過n-1條邊的最短路徑。

#include
#include
#include

using namespace std;

struct Edge
{
    int from;    //邊起點
    int to;      //邊終點
    int weight;  //邊權重
};

int main(void)
{
    int v = 5;  //頂點數
    int e = 5;  //邊數

    const int INT_INF = INT_MAX - 10000;  //防止溢出的最大值

    vector dis(v);
    //以0為源點，初始化
    for (int i = 0; i < v; ++i)
        dis[i] = INT_INF;
    dis[0] = 0;

    vector edges = {
        {1, 2, 2},
        {0, 1, -3},
        {0, 4, 5},
        {3, 4, 2},
        {2, 3, 3}
    };

    //Bellman-Ford
    for (int turn = 0; turn < v - 1; ++turn)
    {
        vector detect = dis;  //備份

        for (const auto & edge : edges)
        {
            if (dis[edge.to] > dis[edge.from] + edge.weight)
                dis[edge.to] = dis[edge.from] + edge.weight;
        }

        if (detect == dis)  //如果dis數組沒有更新，提前退出循環結束算法
            break;
    }

    for (const auto & point : dis)
        cout << point << ' ';
    cout << endl;

    //檢測負權回路
    bool isloop = false;
    for (const auto & edge : edges)
        if (dis[edge.to] > dis[edge.from] + edge.weight)
            isloop = true;
    cout << (isloop ? "存在" : "不存在") << "回路" << endl;

    return 0;
}

Bellman-Ford算法可以檢測一個圖是否含有負權回路。如果在進行n-1輪松弛之後，仍然可以繼續成功松弛，那麼此圖必然存在負權回路。（如果一個圖沒有負權回路，那麼最短路徑所包含的邊最多為n-1條，即進行n-1輪松弛之後最短路徑不會再發生變化。如果在n-1輪松弛之後，最短路徑仍然會發生變化，則該圖必然存在負權回路。）

Bellman-Ford算法的時間復雜度是O(NM)（比Dijkstra算法還高？），可以繼續優化。在實際操作中，Bellman-Ford算法經常會在未達到n-1輪松弛前就已經計算出最短路徑（n-1只是最大值）。因此可以添加一個數組來備份dis，如果在新一輪的松弛中數組dis沒有發生變化，則可以提前跳出循環。（優化的前提基於整個數組沒有變化）

另一種優化：在每實施一次松弛操作後，就會有一些頂點已經求得其最短路徑，此後這些頂點的最短路徑的估計值就會一直保持不變，不再受後續松弛操作的影響，但是每次還要判斷是否需要松弛，這裡浪費了時間。這就啟發：每次僅對最短路徑估計值發生變化了的頂點的所有出邊執行松弛操作。

美國應用數學家Richard Bellman於1958年發表了該算法。此外Lester Ford，Jr.在1956年也發表了該算法。其實Edward F.Moore（提出廣度優先搜索算法）在1957年也發表了同樣的算法，所以這個算法也成為Bellman-Ford-Moore算法。

Bellman-Ford的隊列優化

每次僅對最短路徑發生了變化的點的相鄰邊執行松弛操作。

每次選取隊首頂點u，對u的所有出邊進行松弛操作。假如有一條u->v的邊，如果通過u->v這條邊使得源點到頂點v的最短路程變短（dis[u] + e[u][v] < dis[v]），且v不在當前隊列中，就將v放入隊尾。

同一個頂點同時在隊列中出現多次是毫無意義的，所以需要一個數組來判重（判斷哪些點已經在隊列中）。在對頂點u的所有出邊松弛完畢後，就將頂點v出隊。接下來不斷從隊列中取出新的隊首頂點再進行以上操作，直至隊列空為止。

#include
#include
#include
#include
#include

using namespace std;

struct Edge
{
    int from;    //邊起點
    int to;      //邊終點
    int weight;  //邊權重
};

int main(void)
{
    int v = 5;  //頂點數
    int e = 7;  //邊數

    const int INT_INF = INT_MAX - 10000;  //防止溢出的最大值

    vector dis(v);
    queue vex_opt;  //bellman-ford優化隊列
    vector flags(v, false);  //標記點是否在隊列中

    vector> graph(v);  //list和forward_list也行
    graph[0].push_back({ 0, 1, 2 });
    graph[0].push_back({ 0, 4, 10 });
    graph[1].push_back({ 1, 2, 3 });
    graph[1].push_back({ 1, 4, 7 });
    graph[2].push_back({ 2, 3, 4 });
    graph[3].push_back({ 3, 4, 5 });
    graph[4].push_back({ 4, 2, 6 });

    //以0為源點，初始化
    for (int i = 0; i < v; ++i)
        dis[i] = INT_INF;
    dis[0] = 0;
    flags[0] = true;
    vex_opt.push(0);

    //判斷是否存在負權回路
    vector loop(v, 0);
    ++loop[0];

    while (!vex_opt.empty() && find(loop.begin(), loop.end(), v) == loop.end())
    //隊列不為空和沒檢測出負權回路的時候循環
    {
        //掃描當前頂點的所有邊
        for (const auto & edge : graph[vex_opt.front()])
        {
            //判斷是否松弛成功
            if (dis[edge.to] > dis[edge.from] + edge.weight)
            {
                dis[edge.to] = dis[edge.from] + edge.weight;
                //判斷頂點是否在隊列中
                if (flags[edge.to] == false)
                {
                    //入隊
                    flags[edge.to] = true;
                    vex_opt.push(edge.to);
                    ++loop[edge.to];
                }
            }
        }
        //出隊
        flags[vex_opt.front()] = false;
        vex_opt.pop();
    }

    if (vex_opt.empty())
    {
        for (const auto & point : dis)
            cout << point << ' ';
        cout << endl;
        cout << "不存在負權回路" << endl;
    }
    else
    {
        cout << "存在負權回路" << endl;
    }

    return 0;
}

初始時將源點加入隊列。每次從隊首取出一個頂點，並對與其相鄰的所有頂點進行松弛嘗試，若某個相鄰的頂點松弛成功，且這個相鄰的頂點不在隊列中，則將它加入到隊列中。對當前頂點處理完畢後出隊，並對下一個新隊首進行如上操作，直到隊列為空時算法結束。

使用隊列優化的Bellman-Ford算法在形式上和廣度優先搜索非常類似，不同的是在廣度優先搜索的時候一個頂點出隊後通常就不會再重新進入隊列。而這裡一個頂點很可能在出隊列之後再次被放入隊列，也就是當一個頂點的最短路程估計值變小後，需要對其所有出邊進行松弛，但是如果這個頂點的最短路程再次變小，仍需要對其所有出邊再次進行松弛，這樣才能保證相鄰頂點的最短路程估計值同步更新。

使用隊列優化的Bellman-Ford算法的時間復雜度在最壞情況下也是O(MN)。

通過隊列優化的Bellman-Ford算法如何判斷一個圖是否有負環呢？

如果某個點進入隊列的次數超過n次，那麼這個圖肯定存在負環。

用隊列優化的Bellman-Ford算法的關鍵之處在於：只有那些在前一遍松弛中改變了最短路程估計值的頂點，才可能引起它們鄰接點最短路程估計值發生變化。因此，用一個隊列來存放被松弛成功的頂點，之後只對隊列中的點進行處理，這就降低了算法的時間復雜度。

最短路徑算法對比分析

Floyd Dijkstra Bellman-Ford 隊列優化Bellman-Ford 空間復雜度 O(N^2) O(M) O(M) 時間復雜度 O(N^3) O((M+N)logN) O(MN) 適用情況 稠密圖，和頂點關系密切 稠密圖，和頂點關系密切 稀疏圖，和邊關系密切 負權 可以解決負權 不能解決負權 可以解決負權

Floyd算法雖然總體時間復雜度高，但是可以解決負權邊，並且均攤到每一點對上，在所有的算法中還是屬於較優的，另外，較小的編碼復雜度也是一大優勢。所以，如果要求的是所有點對間的最短路徑，或者如果數據范圍較小，則Floyd算法比較適合。

Dijkstra算法最大的弊端是它無法適應有負權邊的圖，但是Dijkstra具有良好的可擴展性，擴展後可以適應很多問題。另外用堆優化的Dijkstra算法的時間復雜度可以達到O((M+N)logN)。

當邊有負權時，需要使用Bellman-Ford算法或者隊列優化的Bellman-Ford算法。