Bellman-Ford算法的改進：SPFA算法

一、算法簡介

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 . . .