SPFA算法

/* 由于Bellman-Ford算法的每轮操作都需要操作所有的边，显然这其中会有大量无意义的操作， 严重影响了算法的性能。于是注意到，只有当某个顶点u的d[u]值改变时，从它出发的边的邻接 点v的d[v]值才有可能改变。由此可以进行一个优化：建立一个队列，每次将队首顶点取出，然 后对从u出发的所有边u->v进行松弛操作，也就是判断d[u]+length[u->v]<d[v]是否成立， 如果成立，则用d[u]+length[u->v]覆盖d[v]，于是d[v]获得更优的值，此时如果v不在队列 中，就把v加入队列。这样操作直到队列为空（说明图中没有从源点可达的负环），或某个顶点 的入队次数超过V-1（说明图中存在从原点可达的负环）。以下是伪代码： queue<int> Q; 源点s入队; while(队列非空) { 取出队首元素u； for(u的所有邻接边u->v) { if(d[u]+dis<d[v]) { d[v] = d[u] +　dis; if(v当前不在队列) { v入队； if(v入队次数大于n-1) { 说明有可达负环，return; } } } } } 这种优化后的算法被称为SPFA（Shortest Path Faster Algorithm）,期望时间复杂度为O(kE), k为常数，很多情况下不超过2，经常性优于堆优化的Dijkstra算法。若原图中存在从源点可达的负环 则SPFA的时间复杂度会退化成O(VE)。 */ //下面是邻接表形式的图的SPFA代码 #include<vector> #include<queue> #include<algorithm> using namespace std; const int MAXV = 1000; const int INF = 1000000000; struct Node { int v, dis; }; vector<Node> Adj[MAXV];//图G的邻接表 int n, d[MAXV], num[MAXV];//num数组记录顶点的入队次数 bool inq[MAXV];//顶点是否在队列中 bool SPFA(int s) { //初始化部分 memset(inq, false, sizeof(inq)); memset(num, 0, sizeof(num)); fill(d, d + MAXV, INF); //源点入队部分 queue<int>Q; Q.push(s);//源点入队 inq[s] = true;//源点已入队 num[s]++;//源点入队次数加1 d[s] = 0;//源点的d值为0 //主体部分 while (!Q.empty()) { int u = Q.front();//队首顶点编号为u Q.pop();//出队 inq[u] = false;//设置u为不在队列中 //遍历u的所有邻接边v for (int j = 0; j < Adj[u].size(); j++) { int v = Adj[u][j].v; int dis = Adj[u][j].dis; //松弛操作 if(d[u]+dis<d[v]) { d[v] = d[u] + dis; if (!inq[v])//如果v不在队列中 { Q.push(v);//v入队 inq[v] = true;//设置v为在队列中 num[v]++;//v的入队次数加1 if (num[v] >= n) return false;//有可达负环 } } } } return true;//无可达环 } /* 注意上述SPFA代码是BFS版本，当然也可以将队列换成栈以实现DFS版本的SPFA，对判环有奇效。 还有，可以将队列换成优先队列以加快速度。当然还可以换成deque（双端队列），使用SLF或 LLL优化。 SPFA算法有两个优化算法 SLF 和 LLL： SLF：Small Label First 策略，设要加入的节点是j，队首元素为i， 若dist(j)<dist(i)，则将j插入队首，否则插入队尾。 LLL：Large Label Last 策略，设队首元素为i，队列中所有dist值 的平均值为x，若dist(i)>x则将i插入到队尾，查找下一元素，直到找 到某一i使得dist(i)<=x，则将i出对进行松弛操作。SLF 可使速度 提高 15 ~ 20%；SLF + LLL 可提高约 50%。 在实际的应用中SPFA的算法时间效率不是很稳定，为了避免最坏情况的 出现，通常使用效率更加稳定的Dijkstra算法。 */