BF算法的优化之SPFA算法

介绍

全称Shortest Path Faster Algorithm.

优化思想：

1.由int path[maxn]定义的记录最短距离的容器，只有在path[i]+value<path[j]时才会更新，它们两者的值相等时path的值仍保持不变。由此优化容器，选择用一个队列来替path数组辅助记录最短路径。
2.优化BF算法判断负环：
如果最短路径未在队列中，则加入，入队次数累加，直至队列为空时结束。其中，如果一个顶点的入队次数超过顶点个数V-1,说明在进行V-1趟比较操作后，仍存在更小的路径，即图中存在从源点可达的负环。

实现

const int maxn=100;
const int INF=1000000000;
int path[maxn],num[maxn];
bool isin[maxn]={false};//是否在队列中
struct node{int v;int value;
};
vector<node> table[maxn];
int n;//顶点个数bool SPFA(int b){fill(path,path+maxn,INF);memset(num,0,sizeof(num));queue<int> q;q.push(b);path[b]=0;num[b]++;//记录入队次数isin[b]=true;while(!q.empty()){int front=q.front();q.pop();num[front]--;isin[front]=false;//边记录边判断:以出队元素为中心展开for(int j=0;j<table[front].size();j++){int v=table[front][j].v;int value=table[front][j].value;if(path[front]+value<path[v]){if(!isin[v]){//最优路径不在队列中q.push(v);//入队num[v]++;isin[v]=true;if(num[v]>=n)//存在负环return false;}}}}}return true;
}