弥补了Dijskla的缺陷:
A->B的Dijskla算法在出现负数的时候出现判断错误。
image.png
image.png
问题的原因:
之所以出现问题不是因为有负值出现,而是因为有负环出现。
以上面的情况为例:
1. 第一轮刚开始:
image.png2. 第一轮遍历结束:
image.png3. 第二轮结束:
image.png每遍历一次最短路径就会比原来少一点,无法稳定。
优化的SPFA(Shortest Path Faster)算法:
-
如果有闭环,则dis[choosed]>distance总需要不断更新。总是会有新的节点push然后pop,最后陷入死循环,直到counts[choosed]>=点数,触发警告跳出循环,因为入栈次数最多不超过点数(即最高为points-1)。
-
如果没闭环,则dis[choosed]>distance更新停止。不会有新的节点进入,pop之后empty退出循环。
时间复杂度为O(K*E),E为边数,K为一个常数,通常小于等于2。
需要的标记量:
queue<int>q; // 缓存已占领的节点队列
int dis[N]={0}; // 记录到源点的距离
bool occupy[N]={false}; // 是否在queue中
int counts[N]={0}; // 计算同一个节点的入栈次数,>=n即有负环出现,return ;
示例代码:
#include <bits/stdc++.h>
using namespace std;
typedef struct{
int num; // 在BFS中第一列[0]中作为记录上次遍历的位置
int length; // 长度
}Node;
#define N 100000
int dis[N]={0}; // 记录到源点的距离
bool occupy[N]={false}; // 是否在queue中
int counts[N]={0}; // 计算同一个节点的入栈次数,>=n即有负环出现,return ;
int points=0; // 记录点数
int edges=0,begining,ending;
vector<vector<Node>>v;
// 思路:BFS暴力穷举所有的边,进行全局优化。
int bellman(vector<vector<Node>>v,int begining){
int i=0,j=0;
queue<int>q;
q.push(begining);
counts[begining]++;
// 入栈时访问计数器++
while(!q.empty()){
int t=q.front();
q.pop();
occupy[t]=false;
// 标记为出栈
for(i=0;i<v[t].size();i++){
int choosed=v[t][i].num;
if(!occupy[choosed]){
int distance=dis[t]+v[t][i].length;
if(dis[choosed]>distance){
occupy[choosed]=true;
// 标记入栈
q.push(choosed);
counts[choosed]++;
// 入栈计数器++
dis[choosed]=distance;
// 更新路径
// 入栈次数>=点数则报错
if(counts[choosed]>=points){
return 2;
}
}
}
}
}
return 1;
}
void insert(vector<vector<Node>>&v,int point1,int point2,int length){
Node node;
node.num=point2;
node.length=length;
v[point1].push_back(node);
}
int main(){
int i,j;
scanf("%d %d %d %d",&points,&edges,&begining,&ending);
int point1,point2,length;
for(i=0;i<points;i++){
dis[i]=N;
vector<Node>vv;
v.push_back(vv);
}
dis[begining]=0;
// 起始点的距离设为0,其他设为无穷大。
for(i=0;i<edges;i++){
scanf("%d %d %d",&point1,&point2,&length);
insert(v,point1,point2,length);
}
int ans=bellman(v,begining);
cout<<"ans:"<<ans<<endl;
if(ans==2){
cout<<"Has negative ring!"<<endl;
return 0;
}
cout<<"-------"<<endl;
for(i=0;i<points;i++){
cout<<">>>"<<dis[i]<<" ";
}
}
/*
3 3 0 2
0 1 5
1 2 3
2 0 -10
*/
网友评论