一、算法簡介
SPFA算法全稱是最短路徑快速算法(Shortest Path Faster Algorithm),是基于Bellman-Ford算法的隊列優化。SPFA算法能和Bellman-Ford算法一樣,可以處理帶負權值邊的圖,但是複雜度要小很多。
一般認為,此算法的時間複雜度為O(ke),其中k為所有頂尖進隊的平均次數,可以證明k一般不超過2。
原來的Bellman-Ford算法,對圖進行 |V|-1 次周遊,多了很多沒有必要的操作。現在考慮用一個隊列來優化,若頂點v的最短路徑改變了,則将此頂點入隊。下一次周遊從該頂點出發到所有鄰接頂點的邊,進行松弛操作,也隻将更新了最短路徑的邊入隊。
二、僞代碼實作
wikipedia的版本
procedure Shortest-Path-Faster-Algorithm(G, s)
1 for each vertex v ≠ s in V(G)
2 d(v) := ∞
3 d(s) := 0
4 offer s into Q
5 while Q is not empty
6 u := poll Q
7 for each edge (u, v) in E(G)
8 if d(u) + w(u, v) < d(v) then
9 d(v) := d(u) + w(u, v)
10 if v is not in Q then
11 offer v into Q
三、C++實作
/*
* @ spfa.cpp
* @author Halfish Zhang
* @version 1.0 2014/5/24
*/
#include <iostream>
#include <queue>
#include <vector>
#include <stack>
using namespace std;
// 最大的頂點數
const int MAX_NUM = 2014;
// 定義常量無窮大
const int INF_NUM = 0x3f3f3f3f;
// 用鄰接連結清單來存儲邊
struct Edge
{
int v;
int weight;
};
// 鄰接表用vector來存儲比較合适
vector<Edge> edges[MAX_NUM * 2];
int vertexNum, edgeNum; // 實際的頂點數和邊數
int source; // 源點
int dist[MAX_NUM], pred[MAX_NUM]; // dist[i]用來存放從 source 到 i 的最短距離,pred[i]為最短路徑的前驅
bool inQueue[MAX_NUM]; // inQueue[i]存放頂點 i 是否在隊列中
int pushCount[MAX_NUM]; // pushCount[i] 表示頂點 i 被放進隊列的次數
queue<int> q;
bool spfa()
{
// init
for(int i = 1; i <= vertexNum; ++ i)
{
dist[i] = INF_NUM;
pred[i] = -1;
inQueue[i] = false;
pushCount[i] = 0;
}
dist[source] = 0;
// push source into queue
q.push(source);
inQueue[source] = true;
pushCount[source] = 1;
while(!q.empty())
{
// cur means current vertex
int curr = q.front();
q.pop();
inQueue[curr] = false;
// edges[curr]是一個vector,裡面放着和curr相鄰的邊Edge。
int len = edges[curr].size(); //共len個頂點與curr相鄰
for(int i = 0; i < len; ++ i)
{
Edge *edges_vec = &edges[curr][i]; // 用edges_vec表示第i條邊,便于尋址
// 松弛操作 relax
if(dist[(*edges_vec).v] > dist[curr] + (*edges_vec).weight )
{
dist[(*edges_vec).v] = dist[curr] + (*edges_vec).weight;
pred[(*edges_vec).v] = curr;
// 若不在隊列中,需要加入隊列
if(!inQueue[(*edges_vec).v])
{
q.push((*edges_vec).v);
inQueue[(*edges_vec).v] = true;
pushCount[(*edges_vec).v] ++;
// 如果入隊列的次數超過vertexNum,說明存在負權值cycle
if(pushCount[(*edges_vec).v] > vertexNum)
{
// 釋放記憶體?
while(!q.empty()) {
q.pop();
}
return false;
}
}
}
}
}
return true;
}
void print(int i)
{
cout << "The path from " << source << " to " << i << " is : " << endl;
stack<int> s;
s.push(i);
while(s.top() != source) {
s.push(pred[s.top()]);
}
int len = s.size();
for(int i = 0; i < len; ++ i) {
cout << s.top() << " ";
s.pop();
}
cout << endl << endl;
}
int main(int argc, char const *argv[])
{
cout << "Please input the vertexNum, edgeNum and source:" << endl;
cin >> vertexNum >> edgeNum >> source;
cout << "Please input the " << edgeNum ;
cout << " edges, which from u to v with weight of w" << endl;
int u1, v1, w1;
Edge temp;
for(int i = 0; i < edgeNum; ++ i)
{
cout << i + 1 << " : ";
cin >> u1 >> v1 >> w1;
temp.v = v1;
temp.weight = w1;
edges[u1].push_back(temp);
}
if( spfa() )
{
cout << endl << endl;
cout << "The minimum weight of these paths from " << source << " are: " << endl;
for(int i = 1; i <= vertexNum; ++ i)
cout << dist[i] << " ";
cout << endl << endl;
cout << "All these paths are as follows: " << endl;
for(int i = 1; i <= vertexNum; ++ i)
print(i);
} else {
cout << "Sorry, no shortest path exist, ";
cout << "because there are some nagetive cycles" << endl;
}
return 0;
}
四、測試樣例
見下圖
輸入樣例:
6 9 1
1 2 7
1 3 9
1 6 14
2 3 10
2 4 15
3 4 11
3 6 2
4 5 6
5 6 9
輸出樣例
The minimum weight of these paths from 1 are:
0 7 9 20 26 11
All these paths are as follows:
The path from 1 to 1 is :
1
The path from 1 to 2 is :
1 2
The path from 1 to 3 is :
1 3
The path from 1 to 4 is :
1 3 4
The path from 1 to 5 is :
1 3 4 5
The path from 1 to 6 is :
1 3 6
--------------------------------
Process exited with return value 0
Press any key to continue . . .