天天看點
傳回

最短路問題（Floyd、Bellman-Ford算法、SPFA算法、Dijkstra算法）+列印路徑

最短路問題分為兩類：單源最短路和多源最短路。前者隻需要求一個固定的起點到各個頂點的最短路徑，後者則要求得出任意兩個頂點之間的最短路徑。我們先來看多源最短路問題。

Floyd算法 

int dist[400][400];
void Floyd(int n)
{
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

Floyd本質上是一個動态規劃的思想，每一次循環更新經過前k個節點，i到j的最短路徑。

這甚至不需要特意存圖，因為dist數組本身就可以從鄰接矩陣拓展而來。初始化的時候，我們把每個點到自己的距離設為0，每新增一條邊，就把從這條邊的起點到終點的距離設為此邊的邊權（類似于鄰接矩陣）。其他距離初始化為INF（一個超過邊權資料範圍的大整數，注意防止溢出）。

//Floyd初始化
memset(dist, 63, sizeof(dist));
//利用memset的特性，先把所有距離初始化為0x3f3f3f3f
//注意這個數的兩倍小于32位和64位機器上的INT_MAX
//因為memset是按位初始化的，63就是0x3f，會把int類型初始化為0x3f3f3f3f，即一個很大的整數。
for (int i = 1; i <= n; i++)
    dist[i][i] = 0;
for (int i = 0; i < m; i++)
{
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    dist[u][v] = w;
}

Floyd的時間複雜度顯然是 O ( n 3 ) O(n^3) O(n3)，同時擁有 O ( n 2 ) O(n^2) O(n2) 的空間複雜度（n表示點數，m表示邊數），都比較高，是以隻适用于資料規模較小的情形。

一般而言，我們更關心的是單源最短路問題，因為當起點被固定下來後，我們可以使用更快的算法。

Bellman-Ford算法

因為起點被固定了，我們現在隻需要一個一維數組dist[]來存儲每個點到起點的距離。若1為起點，我們初始化時把dist[1]初始化為0，其他初始化為INF。

我們要找到從起點到某個點的最短路，設起點為S，終點為D，那這條最短路一定是S->P1->P2->…->D的形式，假設沒有負權環，那這條路徑上的點的總個數一定不大于n。

現在我們定義對點x, y的松弛操作是：

dist[y] = min(dist[y], dist[x] + e[x][y]);
//這裡的e[x][y]表示x、y之間的距離，具體形式可能根據存圖方法不同而改變

松弛操作就相當于考察能否經由x點使起點到y點的距離變短。

而Bellman-Ford算法實質就是：

把所有邊松弛n-1遍！

這是種很暴力的算法，它的時間複雜度是 O ( n m ) O(nm) O(nm)。

void Bellman_Ford(int n, int m)
{
    for (int j = 0; j < n - 1; j++)
        for (int i = 1; i <= m; i++)
            dist[edges[i].to] = min(dist[edges[i].to], dist[edges[i].from] + edges[i].w);
            //松弛操作，n個點，m個邊
}

這裡用的是鍊式前向星存圖，但是建議存的時候多存一個from，友善周遊所有邊。當然其實并沒什麼必要，這裡直接暴力存邊集就可以了，因為這個算法并不關心每個點能連上哪些邊。

我們之前說，我們不考慮負權環，但其實Bellman-Ford算法是可以很簡單地處理負權環的，隻需要再多對每條邊松弛一遍，如果這次還有點被更新，就說明存在負權環。因為沒有負權環時，最短路上的頂點數一定小于n，而存在負權環時，可以無數次地環繞這個環，最短路上的頂點數是無限的。

SPFA算法

O ( n m ) O(nm) O(nm)的複雜度顯然還是太高了，現在我們想想，能不能别這麼暴力，每次不松弛所有點，而隻松弛可能更新的點？

我們觀察發現，第一次松弛S, P1時，可能更新的點隻可能是S能直接到達的點。然後下一次可能被更新的則是S能直接到達的點能直接到達的點。SPFA算法正是利用了這種思想。

SPFA算法，也就是隊列優化的Bellman-Ford算法，維護一個隊列。

據說随機資料下期望時間複雜度是 O ( n + log ⁡ n ) O(n+\log n) O(n+logn)。

總結一下，SPFA是如何做到“隻更新可能更新的點”的？

  1. 隻讓目前點能到達的點入隊
  2. 如果一個點已經在隊列裡，便不重複入隊

  3. 如果一條邊未被更新，那麼它的終點不入隊

    我們用一個inqueue[]數組來記錄一個點是否在隊列裡，于是SPFA的代碼如下：

void SPFA(int s)
{
    queue<int> Q;
    Q.push(s);
    while (!Q.empty())
    {
        int p = Q.front();
        Q.pop();
        inqueue[p] = 0;
        for (int e = head[p]; e != 0; e = edges[e].next)
        {
            int to = edges[e].to;
            if (dist[to] > dist[p] + edges[e].w)
            {
                dist[to] = dist[p] + edges[e].w;
                if (!inqueue[to])
                {
                    inqueue[to] = 1;
                    Q.push(to);
                }
            }
        }
    }
}

這個算法已經可以A掉洛谷P3371的單源最短路徑（弱化版）了。然而它的時間複雜度不穩定，最壞情況可以被卡成Bellman-Ford，也就是 O ( n m ) O(nm) O(nm)。現在不少最短路的題會刻意卡SPFA，是以會有大佬說：SPFA死了。然而這仍然不失為一種比較好寫、通常也比較快的算法。

SPFA也可以判負權環，我們可以用一個數組記錄每個頂點進隊的次數，當一個頂點進隊n次時，就說明存在負權環。（這與Bellman-Ford判負權環的原理類似）

Dijkstra算法

下面介紹一種複雜度穩定的算法：Dijkstra算法。

Dij基于一種貪心的思想，我們假定有一張沒有負邊的圖。首先，起點到起點的距離為0，這是沒有疑問的。現在我們對起點和它能直接到達的所有點進行松弛。

因為沒有負邊，這時我們可以肯定，離起點最近的那個頂點的dist一定已經是最終結果。為什麼？因為沒有負邊，是以不可能經由其他點，使起點到該點的距離變得更短。

那現在我們來考察2号點：

我們對2号點和它能到達的點進行松弛。這時dist儲存的是起點直接到達或經由2号點到達每個點的最短距離。我們這時候取出未通路過的dist最小的點（即4号點），這個點的dist也不可能變得更短了（因為其他路徑都至少要從起點直接到達、或者經由2号點到達另一個點，再從這另一個點到達4号點）。

繼續這個流程，松弛4号點能到達的點：

然後分别考察3、5号點，直到所有點都被通路過即可。

總結一下，Dijkstra算法的流程就是，不斷取出離頂點最近而沒有被通路過的點，松弛它和它能到達的所有點。

如何取出離頂點最近的點？如果暴力尋找，那就是樸素的Dijkstra算法，時間複雜度是 O ( n 2 ) O(n^2) O(n2)，但我們可以采取堆優化。具體而言，我們可以用一個優先隊列（或手寫堆，那樣更快）來維護所有節點。這樣可以實作在 O ( m log ⁡ n ) O(m\log n) O(mlogn) 的時間内跑完最短路。

首先寫一個結構體：

struct Polar{
    int dist, id;
    Polar(int dist, int id) : dist(dist), id(id){}
};

然後寫一個仿函數（也可以用重載Polar的小于運算符代替），再建構優先隊列：

struct cmp{
    bool operator ()(Polar a, Polar b){ // 重載()運算符，使其成為一個仿函數
        return a.dist > b.dist;    // 這裡是大于，使得距離短的先出隊
    }
};
priority_queue<Polar, vector<Polar>, cmp> Q;

Dijkstra算法的實作：

void Dij(int s)
{
    dist[s] = 0;
    Q.push(Polar(0, s));
    while (!Q.empty())
    {
        int p = Q.top().id;
        Q.pop();
        if (vis[p])
            continue;
        vis[p] = 1;
        for (int e = head[p]; e != 0; e = edges[e].next)
        {
            int to = edges[e].to;
            dist[to] = min(dist[to], dist[p] + edges[e].w);
            if (!vis[to])
                Q.push(Polar(dist[to], to));
        }
    }
}

當然，也有一種簡化的寫法，利用STL裡的pair：

typedef pair<int, int> Pair;
priority_queue<Pair, vector<Pair>, greater<Pair> > Q;

這樣的代碼與原來隻有三行的差別：

void Dij(int s)
{
    dist[s] = 0;
    Q.push(make_pair(0, s));
    while (!Q.empty())
    {
        int p = Q.top().second;
        Q.pop();
        if (vis[p])
            continue;
        vis[p] = 1;
        for (int e = head[p]; e != 0; e = edges[e].next)
        {
            int to = edges[e].to;
            dist[to] = min(dist[to], dist[p] + edges[e].w);
            if (!vis[to])
                Q.push(make_pair(dist[to], to));
        }
    }
}

但還是省去了寫結構體和仿函數的步驟，因為pair已經内建了比較函數。

也許你會想，每個步驟不是應該取目前離源點最近、且未被通路過的元素嗎，但我們現在每次讓一個pair進入優先隊列，這時pair裡面存儲的dist是那時該點到源點的距離，我怎麼能保證每次取出來的點恰是離源點最近的點呢？

其實是這樣的，在一個點被通路前，優先隊列裡會存儲這個點被更新的整個曆史。

注意：堆優化Dij雖然複雜度穩定且較低，但是不能處理負邊。原因很明顯，如果有負邊，就不能保證離源點最近的那個點的dist不會被更新了。

列印路徑

我們隻需要用一個pre[]數組存儲每個點的父節點即可。（單源最短路的起點是固定的，是以每條路有且僅有一個祖先節點，一步步溯源上去的路徑是唯一的。相反，這裡不能存子節點，因為從源點下去，有很多條最短路徑）

每當更新一個點的dist時，順便更新一下它的pre。這種方法對SPFA和Dij都适用，以下是對SPFA的修改：

if (edges[e].w + dist[p] < dist[to])
{
    pre[to] = p;    //在這裡加一行
    dist[to] = edges[e].w + dist[p];
    if (!inqueue[to])
    {
        Q.push(to);
        inqueue[to] = 1;
    }
}

列印（以列印從1到4的最短路為例）：

int a = 4;
while (a != 1)
{
    printf("%d<-", a);
    a = pre[a];
}
printf("%d", a);

這樣列印出的結果是反向的箭頭，如果想得到正向的箭頭，可以先将結果壓入數組再逆序列印。

Dijstra實戰題目講解：

P3371 【模闆】單源最短路徑（弱化版）

P4779 【模闆】單源最短路徑（标準版）

最短路問題 算法 圖論 dijkstra bellman–ford algorithm
上一篇: java最大流ford_Ford-Fulkerson 最大流算法
下一篇: 漫話最短路徑（二）--bellman-Ford（貝爾曼-福特）算法

繼續閱讀