前言
Bellman-Ford算法，限于資料匮乏和時間複雜度比Dijkstra算法高，包括白書在内的很多資料，都沒說得太明白。對于優化後的SPFA算法也沒有提及。
而且最短路問題通常是作為圖論的入門問題，學習者通常沒有圖論基礎，不知道圖論的一些基本常識，看已有的資料很容易産生疑惑。其實，從Bellman-ford算法優化到SPFA算法實際上是順理成章的。
本文旨在闡明這兩個算法思想和步驟，如果有什麼晦澀或者疏漏之處在所難免，煩勞讀者們指出。
這裡是我的個人網站：
https://endlesslethe.com/bellmanford-spfa-tutorial.html
有更多總結分享，最新更新也隻會釋出在我的個人網站上。
排版也可能會更好看一點=v=
Bellman-Ford算法有什麼用
Bellman-Ford算法是用來解決單源最短路問題的。
在現實生活旅遊途中，我們通常想知道一個景點到其他所有景點的最短距離，以友善我們決定去哪些比較近的景點。而這時候，Bellman-Ford算法就有用了。
Bellman-Ford算法的優點是可以發現負圈，缺點是時間複雜度比Dijkstra算法高。
而SPFA算法是使用隊列優化的Bellman-Ford版本，其在時間複雜度和程式設計難度上都比其他算法有優勢。
算法流程
（1）初始化：将除起點s外所有頂點的距離數組置無窮大 d[v] = INF, d[s] = 0
（2）疊代：周遊圖中的每條邊，對邊的兩個頂點分别進行一次松弛操作，直到沒有點能被再次松弛
（3）判斷負圈：如果疊代超過V-1次，則存在負圈
我們用距離數組d[i]來記錄起點s到點i的最短距離。
看了上面的算法流程，通常我們會有四個問題：
- 什麼是松弛操作
- 疊代多少次？
- 疊代的實際意義是什麼？
- 為什麼疊代超過v-1次就存在負圈？
直覺了解松弛操作
如圖，假設選取邊<3,4>來進行松弛操作，那麼進行兩次如下操作（w為邊權）：
d[3] = min(d[3], d[4]+w) // 對點3
d[4] = min(d[4], d[3]+w) // 對點4
這樣做的目的是讓距離數組d盡量的小。
而每一次讓d[i]減小的松弛操作，我們都稱其“松弛成功”。
而實際中，我們使用的松弛操作可以是選取一條邊，也可以是從一個點from到另一個點to。後者對應的松弛操作為：
d[to] = min(d[to], d[from] + w)
從最短路的角度來講，如果對點3的松弛操作成功，意味着從s到4再從4到3這條路比其他從s到3的路都短，距離數組中的d[3]就是目前起點到點3的最短距離。
我們可以總結為：每一次成功的松弛操作，都意味着我們發現了一條新的最短路。
直覺了解疊代
第二第三個問題實際上都是同一個問題：疊代的實際意義是什麼？
這裡我先給出疊代的定義：每次都周遊圖中的所有邊，對每條邊（的兩個端點）都進行松弛操作。
下面，我們以上圖中的點和邊為例，講清楚疊代的實際意義：
第一次疊代
我們很輕易的就找到了兩點對應的最短路。
第二次疊代
我們又找到了新的三個點對應的最短路。
從這次疊代中，我們可以發現一個定理:隻有上一次疊代中松弛過的點才有可能參與下一次疊代的松弛操作。
這裡的“參與”指讓鄰點距離數組d[i]改變。
這個定理很容易了解，如果兩個點的距離數組d[i]在上一次疊代後沒有改變，那麼這次也不會改變。隻有上一次改變了的點才會影響周圍的點。
第三次疊代
這次的示意圖比上兩次都要複雜許多，我給每條邊都标注上了權值，不同疊代中改變過值的點也用不同顔色标注了出來。每條松弛過的邊我也标注了出來。
我們重點注意邊<3,4>中的點3被松弛了，圖中标注為一條虛線。
回憶一下前面的内容，這意味着，我們發現了點3新的最短路，這個最短路經曆了3條邊。
這裡揭示了疊代的實際意義：每次疊代k，我們找到了經曆了k條邊的最短路。
值得注意的是，在疊代還沒結束時的最短路不一定是最終的最短路。有可能最終的最短路經曆的邊很多，但每條邊的權值很小，比經曆邊少的路線距離更短。
第四次疊代
第五次疊代
第六次疊代
注意到沒有點能夠被松弛，根據之前發現的定理“隻有上一次疊代中松弛過的點才有可能參與下一次疊代的松弛操作”，因為不再存在能夠被松弛的點了，疊代結束。
總結
- 定理一：隻有上一次疊代中松弛過的點才有可能參與下一次疊代的松弛操作
- 疊代的實際意義：每次疊代k中，我們找到了經曆了k條邊的最短路。
- “沒有點能夠被松弛”時，疊代結束
根據定理一“隻有上一次疊代中松弛過的點才有可能參與下一次疊代的松弛操作”，似乎算法中周遊每條邊的做法比較菜，我們隻需要考慮那些被成功松弛的點的鄰點不就好了嗎？答案是肯定的。我們可以簡單地通過一個隊列來維護這些被成功松弛的點，這個小小的改進可以帶來巨大加速，改進之後的算法被稱為SPFA。
直覺了解負圈
符合常識地，有定理二：如果在邊權都為正的圖中，最短路一定是一條路徑，而不是一個圈，且長度不會大于等于V
拓展到存在負邊權的圖中，有定理三：對于存在負圈的圖，最短路無意義
定理四：對于不存在負圈的圖，最短路一定是一條路徑，且長度不會大于等于V
如圖所示，因為有邊長為1、-2、-1的負圈存在，起點到其餘所有點的距離都是-INF，因為到其餘所有點的路上都可以經過這個負圈無窮次，這時候最短路沒有意義。
對于Bellman-Ford算法，因為一個最短路如果不存在負圈的話，不會經曆超過V-1條邊，是以假如疊代次數大于等于V，就存在負圈。
Note：網上很多代碼沒有了解每次疊代的意義，采用每個節點的入隊次數來判斷負圈，當然也是可以，但是大大增加了運作時間。
寫在最後
在SPFA的基礎上，我們或許還能進行一些優化，比如參考文獻表中的SLF和LLL，這裡我就不多提了，有興趣可以看一下，就一兩行代碼的事。
希望大家看完本文能夠完全了解SPFA。
Bellman-ford實作代碼
因為這道題點比較少，就使用了鄰接矩陣來儲存圖。實際上，用得比較多的儲存方法是鄰接表和前向星，有興趣了解的戳——“淺談圖的組織（鄰接表、前向星）”【TBC】
/**
* @Date: 28-Jun-2018
* @Email: [email protected]
* @Filename: POJ 3259【bellman-ford】.cpp
@Last modified time: 04-Jul-2018
* @Copyright: ©2018 EndlessLethe. All rights reserved.
*/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
using namespace std;
const int MAXN = 500+10;
int G[MAXN][MAXN];
int d[MAXN];
int vis[MAXN];
bool bellman_ford(int s, int N) {
int flag;
for (int i = 0; i < N; i++) {
flag = 0;//如果不能松弛，則停止
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
if (d[k] > d[j] + G[j][k]) {
d[k] = d[j] + G[j][k];
flag = 1;
}
}
}
if (!flag) return 1;//不存在負環
}
flag = 0;
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
if (d[k] > d[j] + G[j][k]) {
flag = 1;
}
}
}
return !flag;
}
int main() {
int F, N, M, W, S, E, T;
cin >> F;
while (F--) {
memset(G, 0x3f, sizeof(G));
memset(d, 0x3f, sizeof(d));
memset(vis, 0, sizeof(vis));
cin >> N >> M >> W;
for (int i = 0; i < M; i++) {
cin >> S >> E >> T;
S--, E--;
if (T < G[S][E]) G[S][E] = G[E][S] = T;
}
for (int i = 0; i < W; i++) {
cin >> S >> E >> T;
S--, E--;
G[S][E] = -T;
}
if (bellman_ford(0, N)) cout << "NO" << endl;
else cout << "YES" << endl;
}
return 0;
}
SPFA實作代碼
/**
* @Date: 28-Jun-2018
* @Email: [email protected]
* @Filename: POJ 3259【bellman-ford】.cpp
@Last modified time: 04-Jul-2018
* @Copyright: ©2018 EndlessLethe. All rights reserved.
*/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <time.h>
#include <string.h>
#include <queue>
using namespace std;
const int MAXN = 500+10;
int G[MAXN][MAXN];
int d[MAXN];
int vis[MAXN];
queue <int> q;
bool bellman_ford(int s, int N) {
d[s] = 0;
int cnt = 0;
q.push(s);
q.push(cnt);
vis[s] = 1;
while (!q.empty()) {
int x = q.front(); q.pop();
cnt = q.front(); q.pop();
vis[x] = 0;
if (cnt > N) return 0;
for (int i = 0; i < N; i++) {
if (d[i] > d[x] + G[x][i]) {
d[i] = d[x] + G[x][i];
if (!vis[i]) {
q.push(i);
q.push(cnt+1);
vis[i] = 1;
}
}
}
}
return 1;
}
int main() {
int F, N, M, W, S, E, T;
cin >> F;
while (F--) {
while (!q.empty()) q.pop();
memset(G, 0x3f, sizeof(G));
memset(d, 0x3f, sizeof(d));
memset(vis, 0, sizeof(vis));
cin >> N >> M >> W;
for (int i = 0; i < M; i++) {
cin >> S >> E >> T;
S--, E--;
if (T < G[S][E]) G[S][E] = G[E][S] = T;
}
for (int i = 0; i < W; i++) {
cin >> S >> E >> T;
S--, E--;
G[S][E] = -T;
}
if (bellman_ford(0, N)) cout << "NO" << endl;
else cout << "YES" << endl;
}
return 0;
}
題目總結
-
POJ 3259
有重邊，使用鄰接矩陣要注意。算法本身不在乎重邊的情況，使用鄰接表的話，對于蟲洞直接添加一條新的邊即可
- POJ 1860
參考文獻
I. 《挑戰程式設計競賽》
II. Bellman-Ford 算法及其優化
III. 最短路徑算法—Bellman-Ford(貝爾曼-福特)算法分析與實作(C/C++)
IV. SPFA的兩種優化SLF和LLL
V. 請柬（雙向SPFA及SLF LLL優化法模闆題）