本文將介紹三種常見的最短路算法：Dijkstra解愤，F(xiàn)loyd镇饺，SPFA

Dijkstra

Dijkstra是有向圖上的單源最短路徑算法，本質(zhì)是一種貪心送讲。給定一個有向圖G(V奸笤，E)和起點s，基礎(chǔ)的Dijkstra算法會在O(|V|^2)的時間復(fù)雜度內(nèi)求出從s出發(fā)到所有點的最短路長度哼鬓。

Dijkstra算法要求圖中不能有負權(quán)邊监右，其算法描述如下：

1. 建立一個空的優(yōu)先隊列Q；
2. 把所有頂點根據(jù)與s的距離dis[i]插入優(yōu)先隊列异希，其中dis[s]=0健盒，與s不相連的頂點距離設(shè)為INF；
3. 每次從Q中取出與s距離最近的頂點u，對點u的每條出邊e=(u,v)扣癣，更新dis[v] = min(dis[v]惰帽，dis[u] + l(u, v))；
4. 重復(fù)3操作搏色，直到所有頂點都被取出善茎，結(jié)果中dis[i]代表s到i的最短距離。

如果用數(shù)組維護dis[i]频轿，那么每次查找與s最近的點和更新操作代價都是O(|V|)垂涯，算法整體復(fù)雜度O(|V|^2)，這個復(fù)雜度在稠密圖的情況下是很理想的航邢；如果用堆（優(yōu)先隊列）實現(xiàn)耕赘，那么每次查找最近點的代價變成O(lg|V|)，在堆中的decrease-key操作是O(lg|V|)的膳殷，算法中最多有|V|次查找和|E|次更新操骡，算法整體復(fù)雜度O((|V| + |E|) lg|V|)，在稀疏圖中是一種優(yōu)化赚窃。

正確性證明：
Dijkstra每次取出的點都有唯一的“前驅(qū)”册招，因此我們是可以恢復(fù)出一條從起點到終點的路徑的，我們只要證明這條路徑就是達到目標點的最短路徑勒极。采取歸納法證明：

1. 除起點s外第一個被取出的點u找不出比s->u更短的路徑是掰。假如有一條更短的路：s->v...->u，由于不存在負權(quán)邊辱匿，那么l(s,v)<l(s,u)键痛，這與Dijkstra每次取dis最短的點矛盾；
2. 假設(shè)已經(jīng)被取出的點都滿足條件匾七，Dijkstra選中的下一個與s最近的點是v絮短，其前驅(qū)是u（u可能與s重合），那么Dijkstra給出的路徑L1為：s->s1->...->sk->u->v昨忆，其中s1...sk丁频，u都是已經(jīng)被取出的點，其中dis[u]+l(u,v)是最小的邑贴。假設(shè)有一條從s到v的路徑L2長度小于L1限府，那么L2中v的前驅(qū)不能是u（如果是，與歸納假設(shè)矛盾）痢缎，如果不是u胁勺，則只能是一個還沒被取出的點t（如果不是，與剛才dis[u]+l(u,v)的最小性矛盾）独旷，那么此時dis[t]<dis[v]署穗，v不應(yīng)該被從隊列中選取寥裂，矛盾！

dijkstra.jpg

C++實現(xiàn)：

void dijkstra(int s) {  // s: starting vertix
    std::priority_queue<Node, std::vector<Node>, std::greater<Node> > q;
    for(int i = 0; i < n; i++)
        dis[i] = INF;
    dis[s] = 0;
    q.push(std::make_pair(0, s));

    for(int i = 0; i < n; i++) {
        while(!q.empty() && q.top().first > d[q.top().second])
            q.pop();
        // the graph may be unconnected
        if(q.empty()) break;
          
        int hd = q.top().second;
        q.pop();

        for(Edge *p = e[hd]; p; p = p->next)
            if(dis[hd] + p->len < dis[p->dst])
                q.push(std::make_pair(dis[p->dst] = p->len + dis[hd], p->dst));
    }
}

Floyd

Floyd是有向圖上的多源最短路算法案疲，本質(zhì)是動態(tài)規(guī)劃封恰。給定有向圖G(V, E)，F(xiàn)loyd算法可以在O(|V|^3)的時間復(fù)雜度內(nèi)算出圖上任意兩點之間的最短距離褐啡。算法描述如下：

1. 初始化鄰接矩陣dis：i=j時诺舔，dis[i][j] = 0，i != j時备畦，若有從i到j(luò)的有向邊e低飒，dis[i][j]等于e的權(quán)值，若沒有懂盐，dis[i][j] = INF褥赊；
2. 選取一個新的中間節(jié)點k，對于所有的(i, j)對莉恼，如果dis[i][j] < dis[i][k] + dis[k][j]拌喉，則更新dis[i][j]的值為dis[i][k] + dis[k][j]；
3. 重復(fù)操作2俐银，直到所有的點都成為過中間節(jié)點尿背，結(jié)果中dis[i][j]表示i到j(luò)的最短距離。

正確性證明：
Floyd算法中的中間節(jié)點k可以理解為：從起點i到終點j捶惜，只經(jīng)過1-k這些點可以得到的最短路是多少田藐。算法結(jié)束時dis[i][j]對應(yīng)的就是從頂點i到頂點j只經(jīng)過頂點1-|V|的最短路，就是所求的結(jié)果售躁。所以我們只要證明：前k個中間節(jié)點處理完后坞淮，dis[i][j]的值為從起點i只經(jīng)過1-k中的點到達終點j的最短長度茴晋。用歸納法描述：

1. k=1時顯然（dis[i][j]要么是i和j的距離陪捷，要么是i到1的距離加上1到j(luò)的距離，且保證是兩者中較短的）
2. 如果k-1得證诺擅，對于k的情況市袖，從i到j(luò)的最短路要么經(jīng)過k，要么不經(jīng)過k烁涌。經(jīng)過k時苍碟，dis[i][j]會更新為dis[i][k]+dis[k][j]，否則dis[i][j]不變撮执。這兩種情況途徑點的標號都不會超過k微峰，而且由歸納假設(shè)可確保是最短的。

C++實現(xiàn)：

void floyd() {
    // suppose dis matrix is intialized
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[j][k]);
}

因為只是一個三重循環(huán)抒钱，F(xiàn)loyd算法一定會終止蜓肆，那么它是否能處理有負邊的情況呢颜凯？答案是可以的，負邊對我們的歸納并沒有影響仗扬。

SPFA

SPFA(Shortest Path Faster Algorithm)是有向圖上的單源最短路算法症概，它最大的亮點是可以處理負邊，而且在大部分情況下運行效率很高早芭。其算法描述如下：

1. 初始化dis數(shù)組彼城，其中dis[s]為0，其他值為INF退个，初始化一個隊列募壕，其中只有s一個元素；
2. 從隊列中取出第一個元素hd帜乞，對hd的每一條出邊e(hd, i)司抱，更新dis[i] = min(dis[i], dis[hd] + weight[hd][i])，如果dis[i]被更新（更新有時被稱為松弛操作）了且i不在隊列中黎烈，那么把i加入隊列末尾习柠；
3. 重復(fù)2操作直到隊列為空

正確性證明：
SPFA的正確性是三種算法中最不顯然的。首先證明算法是會終止的照棋，向隊列中加入頂點i要求dis[i]被更新為更小的值资溃，而沒有負環(huán)時，dis[i]是有下界的烈炭，即每個點只會被放入隊列有限次溶锭，每一次循環(huán)都會取出一個頂點，所以沒有負環(huán)時符隙，循環(huán)一定會終止趴捅。而在有負環(huán)的時候，SPFA會陷入死循環(huán)霹疫。
接著證明SPFA所得的dis[i]就是從起點s到終點i的最短路拱绑，先證明一個引理：每次檢查隊列是否為空時，所有能引起松弛操作的點都在隊列中丽蝎。

We want to show that if dis[w] > dis[u] + weight[u][w] at the time the condition is checked, u is in the queue. We do so by induction on the number of iterations of the loop that have already occurred. First we note that this certainly holds before the loop is entered: if u!=v, then relaxation is not possible; relaxation is possible from u=v, and this is added to the queue immediately before the while loop is entered. Now, consider what happens inside the loop. A vertex u is popped, and is used to relax all its neighbors, if possible. Therefore, immediately after that iteration of the loop, u is not capable of causing any more relaxations (and does not have to be in the queue anymore). However, the relaxation by u might cause some other vertices to become capable of causing relaxation. If there exists some x such that dis[x] > dis[w] + weight[w][x] before the current loop iteration, then w is already in the queue. If this condition becomes true during the current loop iteration, then either dis[x] increased, which is impossible, or dis[w] decreased, implying that w was relaxed. But after w is relaxed, it is added to the queue if it is not already present.

SPFA算法結(jié)束時隊列為空猎拨，代表沒有松弛操作可以做了。而我們給出一個dis數(shù)組屠阻，它是最短路問題解的充要條件就是不可以再執(zhí)行松弛操作红省。所以SPFA給出的解一定正確的。

時間復(fù)雜度：
段凡丁在提出SPFA的論文中指出SPFA的時間復(fù)雜度是O(|E|)的国觉，但原文的證明很不嚴謹吧恃，關(guān)鍵在于他的一個結(jié)論：平均每個點進入隊列的次數(shù)是一個常數(shù)。我暫時也沒有找到很好的證明麻诀，不過一般認為SPFA的平均時間復(fù)雜度就是O(|E|)的痕寓。值得一說的是缸逃，SPFA在效率上并沒有Dijkstra穩(wěn)定，原因就在于頂點可能多次被加入隊列厂抽，如果很多點都存在“多跳路徑短于少跳路徑”的話需频，SPFA就會變得很慢。

C++實現(xiàn)：

void spfa(int s) {
    std::queue<int> q;
    for(int i = 0; i < n; i++)
        dis[i] = INF;
    dis[s] = 0;
    q.push(s); vis[s] = true;

    while(!q.empty()) {
        int hd = q.front();
        q.pop(); vis[hd] = false;
        for(Edge *p = e[hd]; p; p = p->next)
            if(dis[hd] + p->len < dis[p->dst]) {
                dis[p->dst] = dis[hd] + p->len;
                if(!vis[p->dst])
                    q.push(p->dst), vis[p->dst] = true;
            }
    }
}

附

本文圖片來自 Lecture Slides for Alogorithm Design by Jon Kleinberg and éva Tardos.