單源最短路徑（3）：SPFA 演算法
SPFA（Shortest Path Faster Algorithm）演算法，是西南交通大學段凡丁於 1994 年發表的，其在 Bellman-ford 演算法的基礎上加上一個隊列優化，減少了冗餘的鬆弛操作，是一種高效的最短路演算法。
演算法過程
設立一個隊列用來保存待優化的頂點，優化時每次取出隊首頂點 u，並且用 u 點當前的最短路徑估計值 dist[u] 對與 u 點鄰接的頂點 v 進行鬆弛操作，如果 v 點的最短路徑估計值 dist[v] 可以更小，且 v 點不在當前的隊列中，就將 v 點放入隊尾。這樣不斷從隊列中取出頂點來進行鬆弛操作，直至隊列空為止。（所謂的鬆弛操作，簡單來說，對於頂點 i，把 dist[i] 調整更小。更多解釋請參考百科：鬆弛操作)
而其檢測負權迴路的方法也很簡單，如果某個點進入隊列的次數大於等於 n，則存在負權迴路，其中 n 為圖的頂點數。
程式碼
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
int matrix[100][100]; // 鄰接矩陣
bool visited[100]; // 標記數組
int dist[100]; // 源點到頂點 i 的最短距離
int path[100]; // 記錄最短路的路徑
int enqueue_num[100]; // 記錄入隊次數
int vertex_num; // 頂點數
int edge_num; // 邊數
int source; // 源點
bool SPFA()
{
memset(visited, 0, sizeof(visited));
memset(enqueue_num, 0, sizeof(enqueue_num));
for (int i = 0; i < vertex_num; i++)
{
dist[i] = INT_MAX;
path[i] = source;
}
queue<int> Q;
Q.push(source);
dist[source] = 0;
visited[source] = 1;
enqueue_num[source]++;
while (!Q.empty())
{
int u = Q.front();
Q.pop();
visited[u] = 0;
for (int v = 0; v < vertex_num; v++)
{
if (matrix[u][v] != INT_MAX) // u 與 v 直接鄰接
{
if (dist[u] + matrix[u][v] < dist[v])
{
dist[v] = dist[u] + matrix[u][v];
path[v] = u;
if (!visited[v])
{
Q.push(v);
enqueue_num[v]++;
if (enqueue_num[v] >= vertex_num)
return false;
visited[v] = 1;
}
}
}
}
}
return true;
}
void Print()
{
for (int i = 0; i < vertex_num; i++)
{
if (i != source)
{
cout << source << " 到 " << i << " 的最短距離是：" << dist[i] << "，路徑是：" << i;
int t = path[i];
while (t != source)
{
cout << "--" << t;
t = path[t];
}
cout << "--" << source << endl;
}
}
}
int main()
{
cout << "請輸入圖的頂點數，邊數，源點：";
cin >> vertex_num >> edge_num >> source;
for (int i = 0; i < vertex_num; i++)
for (int j = 0; j < vertex_num; j++)
matrix[i][j] = (i != j) ? INT_MAX : 0; // 初始化 matrix 數組
cout << "請輸入 " << edge_num << " 條邊的資訊：\n";
int u, v, w;
for (int i = 0; i < edge_num; i++)
{
cin >> u >> v >> w;
matrix[u][v] = w;
}
if (SPFA())
Print();
else
cout << "存在負權迴路!\n";
return 0;
}
運行如下：
/* Test 1 */
請輸入圖的頂點數，邊數，源點：5 7 0
請輸入 7 條邊的資訊：
0 1 100
0 2 30
0 4 10
2 1 60
2 3 60
3 1 10
4 3 50
0 到 1 的最短距離是：70，路徑是：1--3--4--0
0 到 2 的最短距離是：30，路徑是：2--0
0 到 3 的最短距離是：60，路徑是：3--4--0
0 到 4 的最短距離是：10，路徑是：4--0
/* Test 2 */
請輸入圖的頂點數，邊數，源點：4 6 0
請輸入 6 條邊的資訊：
0 1 20
0 2 5
3 0 -200
1 3 4
3 1 4
2 3 2
存在負權迴路!
判斷負權迴路的證明
如果某個點進入隊列的次數大於等於 n，則存在負權迴路。為什麼偏偏是 n？
對於一個不存在負權迴路的圖，設其頂點數為 n，我們把圖稍微「轉換」下，如下圖 A：
- 與源點 0 鄰接的點{ 1, 2, 3 }作為第一批次；
- 與第一批次鄰接的點{ 4, 5, 6, 7, 8, 9 }作為第二批次；
- ……
- 與第 k-1 批次鄰接的點{ …… }作為第 k 批次。
其中 k≤n-1，當 k=n-1 時，即為上圖 B。
每操作完一個批次的點，至少有一個點的最短路徑被確定。這裡讀者只需從 Dijkstra 演算法方面來考慮即可。Dijkstra 每次循環都找出 dist[] 里的最小值，可以對應到這裡的每個批次。
一個不存在負權迴路的圖，最多有 n-1 個批次，每做完一個批次至少有一個點的最短路徑被確定，即一個點的入隊次數不超過 n-1。因為若一個頂點要入隊列，則必存在一條權值之和更小的路徑，而在最多做完 n-1 個批次後，所有頂點的最短路徑都被確定。（這裡需要注意的是，如果一個批次中，有多條路徑對某頂點進行更新，則該頂點只會被入隊一次，這從程式碼就可以看出）
時間複雜度
對於一個不存在負權迴路的圖，我們假設其頂點數為 n，邊數為 m。
引自 SPFA 論文：考慮一個隨機圖，運用均攤分析的思想，每個點的平均出度為 \(O(\frac m n)\)，而每個點的平均入隊次數為 2，因此時間複雜度為 \(O(n⋅\frac m n⋅2)=O(2m)=O(m)\)。
關於上述的「平均入隊次數為 2」，2 這個數字從何得來，我也找不到證明，從網上各位朋友對此的一致態度：尚待商榷。但是可以確定的是，SPFA 演算法在隨機圖中的平均性能是優於 Bellman_Ford 演算法的。
SPFA 的最佳時間複雜度為 \(O(n)\)。比如上圖 B，每個點只入隊一次。
接著再看下 SPFA 的最差時間複雜度，它發生在一個完全圖中，如下圖（為突出重點，其餘邊未畫出），
我們約定，0 點為源點，每次更新完 k 點出隊後，k+1 點都可以再次對 k 點進行更新併入隊，其中 1≤ k≤ n-2。那麼我們得出：
0 點，入隊 1 次；
1 點，入隊 n-1 次；
2 點，入隊 n-2 次；
3 點，入隊 n-3 次；
.
n-2 點，入隊 2 次；
n-1 點，入隊 1 次；
因為是完全圖，所以每個點的出度為 n-1，因此總的時間複雜度為：
\]
由於是完全圖，也可以表達成 \(O(nm)\)。很容易看出，SPFA 演算法的時間複雜度很不穩定。
