/*由于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算法。*/
新闻热点
疑难解答