求单源最短路的SPFA算法的全称是：Shortest Path Faster Algorithm。
简单的说就是队列优化的bellman-ford
在路径中存在负权边是 dijkstra 就没法使用了 ，这是就可以SPFA 了
但是当有负权的环是 就没有最短路，spfa 可以判断是否有负权环，如果没有就可以求出最短路。。
期望的时间复杂度O(ke)， 其中k为所有顶点进队的平均次数，可以证明k一般小于等于2。
实现方法：建立一个队列，初始时队列里只有起始点，再建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）。然后执行松弛操作，用队列里有的点去刷新起始点到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空
简单说就是把源点放入队列，然后松弛这个点相连的点，如果松弛成功就把这个点放入队列，用一个数组记录每个点是否在队列中，在一次取出队列中的点，在松弛相连的点，如果松弛成功，就判断这个点是不是在队列中，如果不再队列中就把这个点放入队列（点可能多次进入队列）
spfa 可以判断有无负权环，只需 记录每个点进队的次数，如果超过了 n-1 就有负权环，因为每个点松弛的次数不可能超多n-1
#include "iostream"
#include "vector"
#include "queue"
#include "stack"
#include "fstream"
using namespace std;
struct edge
{
int u;
int v;
int weight;
};
const int maxnum = 20;//节点数目最大值
std::vector<edge> E[maxnum];//边的数组
std::vector<int> dist;//到source的距离
std::queue<int> q;//队列,用于存储在SPFA算法中的需要松弛的节点
std::vector<int> visited;//用于判断该节点是否已经在队列中
std::vector<int> count;//记录入队次数,超过vertexnum则退出
std::vector<int> path;//节点的前继
int vertexnum;//节点数
int edgenum;//边数
const int maxint = 10000;//权重最大值
void initialvector(){// 初始化
dist.resize(vertexnum,maxint);
visited.resize(vertexnum,0);
count.resize(vertexnum,0);
path.resize(vertexnum,-1);
}
void getData(){//获取数据
ifstream in("data");
in>>vertexnum>>edgenum;
initialvector();
int from,to;
double w;
int i = 0;
while(in>>from>>to>>w){
edge temp;
temp.u = from;
temp.v = to;
temp.weight = w;
E[from].push_back(temp);
}
}
bool relax(int u,int v,int weight){
if(dist[v] > dist[u] + weight){
dist[v] = dist[u] + weight;
return true;
}
return false;
}
bool spfa(const int source){
for(int i = 0;i < vertexnum;i++){
dist[i] = (i == source)?0:maxint;
}
q.push(source);
visited[source] = 1;
count[source]++;
while(!q.empty()){
int front = q.front();
q.pop();
for(int i = 0;i < E[front].size();i++){
edge *tmp = &E[front][i];
if(relax((*tmp).u,(*tmp).v,(*tmp).weight)){
path[(*tmp).v] = front;
cout<<front<<" ";
if(visited[(*tmp).v] == 0){
q.push((*tmp).v);
visited[(*tmp).v] = 1;
count[(*tmp).v]++;
if(count[(*tmp).v] > vertexnum){
while(!q.empty()){
q.pop();
}
return false;
}
}
}
}
visited[front] = 0;
}
return true;
}
void Print_Path(int x)
{
stack <int> s;
int w=x;
while(path[w] != -1)
{
s.push(w);
w=path[w];
}
cout<<"顶点 0 到顶点 "<<x<<" 的最短路径长度为："<<dist[x]<<endl;
cout<<"所经过的路径为：0 ";
while(!s.empty())
{
cout<<s.top()<<" ";
s.pop();
}
cout<<endl;
}
int main(int argc, char const *argv[])
{
getData();
int source = 0;
dist[source] = 0;
spfa(0);
Print_Path(1);
}
data：
0 1 6
0 4 7
1 4 8
1 2 5
2 1 -2
3 2 7
1 3 -4
4 3 9
4 2 -3
3 0 2
参考：http://www.cppblog.com/MiYu/archive/2010/10/23/131018.html
http://www.cnblogs.com/scau20110726/archive/2012/11/18/2776124.html