单源最短路之SPFA——Shortest Path Faster Algorithm
???SPFA是目前相当优秀的求最短路径的算法，值得我们掌握。
?? SPFA对Bellman-Ford算法优化的关键之处在于意识到：只有那些在前一遍松弛中改变了距离估计值的点，才可能引
起他们的邻接点的距离估计值的改变。因此，用一个先进先出的队列来存放被成功松弛的顶点。初始时，源点s入队。
当队列不为空时，取出对首顶点，对它的邻接点进行松弛。如果某个邻接点松弛成功，且该邻接点不在队列中，则将其
入队。经过有限次的松弛操作后，队列将为空，算法结束。SPFA算法的实现，需要用到一个先进先出的队列 queue 和
一个指示顶点是否在队列中的 标记数组 mark。为了方便查找某个顶点的邻接点，图采用临界表存储。
?? 需要注意的是：仅当图不存在负权回路时，SPFA能正常工作。如果图存在负权回路，由于负权回路上的顶点无法收
敛，总有顶点在入队和出队往返，队列无法为空，这种情况下SPFA无法正常结束。
判断负权回路的方案很多，世间流传最广的是记录每个结点进队次数，超过|V|次表示有负权
关于SPFA的时间复杂度，一般认为是 O（kE），k一般为2。
如果在判断是否存在负权回路，推荐使用第一种优化形式，否则推荐使用SPFA。
?
//题目要求：判断有无负权环#include <iostream>using namespace std;const int N = 502;const int MAX = INT_MAX;int f;int n;//节点个数为n，边数为2*m+wint m;int w;int queue[N],time[N],dis[N];//循环队列，记录每个节点入队列的次数（大于n表示有负权环），dis记录最短路径值bool vis[N];//true表示在队列中。被松弛的点若在队列中，就不加入队列，出队列后值为falseint pre[N];//节点i发出若干条边，pre[i]表示节点i当前正在遍历的边的前一条边的序号typedef struct{int to;int w;int next;}Edge;Edge e[5201];bool spfa(){int i,j,now,adj;memset(vis,false,sizeof(vis));memset(time,0,sizeof(time));for(i = 2, dis[1] = 0; i <= n; i++)dis[i] = MAX;queue[0] = 1;vis[1] = true;time[1] = 1;int head = 0,tail = 1;while(head != tail){now = queue[head];head = (head + 1) % n;vis[now] = false;for(i = pre[now]; i != -1; i = e[i].next){adj = e[i].to;if(dis[now] != MAX && dis[now] + e[i].w < dis[adj]){if(adj == 1)//若初始点1本身包含负环，直接返回return true;dis[adj] = dis[now] + e[i].w;if(!vis[adj]){queue[tail] = adj;tail = (tail + 1) % n;vis[adj] = true;time[adj] ++;if(time[adj] > n)return true;}}}}return false;}int main(){int i,j,edgeNum;int from,to,w1;cin>>f;for(i = 0; i < f; i++){edgeNum = 0;memset(pre,-1,sizeof(pre));memset(e,0,sizeof(e));cin>>n>>m>>w;for(j = 1; j <= m; j++){cin>>from>>to>>w1;e[edgeNum].to = to; e[edgeNum].w = w1; e[edgeNum].next = pre[from];pre[from] = edgeNum;edgeNum++;e[edgeNum].to = from; e[edgeNum].w = w1; e[edgeNum].next = pre[to];pre[to] = edgeNum;edgeNum++;}for(j = 1; j <= w; j++){cin>>from>>to>>w1;e[edgeNum].to = to; e[edgeNum].w = -w1; e[edgeNum].next = pre[from];pre[from] = edgeNum;edgeNum++;}if(spfa())cout<<"YES\n";elsecout<<"NO\n";}return 0;}????
??? 参见poj3259,1511
?
?