深圳市招投标交易中心网站,加拿大28网站建设,wordpress 安全狗,产品宣传册模板写在前面
由于本人实力尚浅#xff0c;接触算法没多久#xff0c;写这篇blog仅仅是想要提升自己对算法的理解#xff0c;如果各位读者发现什么错误#xff0c;恳请斧正#xff0c;希望和大家一起进步。(●’◡’●)
题目 思路
根据上一篇关于bellman_ford分析的blog接触算法没多久写这篇blog仅仅是想要提升自己对算法的理解如果各位读者发现什么错误恳请斧正希望和大家一起进步。(●’◡’●)
题目 思路
根据上一篇关于bellman_ford分析的blog不了解—传送门)我们知道bellman_ford的解法太暴力了每次都遍历所有的边聪明的你肯定想到了其实bellman_ford算法中很多次松弛是没有意义的因为只有当一个点的前驱结点距离更新时那么该结点才有可能更新只是有可能不一定会更新。想到这一点我们就可以用一个队列queue来存储每次的更新的顶点。先将源点压入队列。只要队列不空我们就取出队头遍历它的所有边依次更新与它相连的点距离源点的距离。如果该顶点距离源点的距离被更新将它入队。
代码
//一些数组的含义说明
int e[N],ne[N],h[N],w[N]; //建立邻接表
int d[N]; //存储每一个顶点距离源点的距离初始化为INF
int st[N]; //记录每一个顶点是否在队列中1表示在队列中0表示不在队列中#includeiostream
#includecstring
#includequeueusing namespace std;
const int N100010;
int n,m;
int e[N],ne[N],h[N],w[N],d[N],st[N],idx;void add(int a,int b,int c)
{e[idx]b,ne[idx]h[a],w[idx]c,h[a]idx;
}void spfa()
{queueint q; q.push(1); //将源点压入队列d[1]0; //同时将源点距离自己本身的距离置为0st[1]1; //由于源点已经入队所以源点的状态置为1while(!q.empty()) //只要队列不空就一直循环下去{int tq.front();q.pop();st[t]0; //由于已经将该顶点取出沪所以又将该点的状态置为0方便后续再次入队for(int ih[t];i!-1;ine[i]) //遍历与该顶点相连的所有顶点{int je[i];if(d[j]d[t]w[i]) {d[j]d[t]w[i];if(!st[j]){st[j]1;q.push(j); //如果距离被更新且该点不在队列中就将该点压入队列}}}}
}int main()
{cinnm;memset(h,-1,sizeof h); //邻接表的初始化memset(d,0x3f,sizeof d); //距离数组的初始化while(m--){int a,b,c;cinabc;add(a,b,c);}spfa();if(d[n]0x3f3f3f3f)coutimpossibleendl;elsecoutd[n]endl;return 0;
}说明
st[]数组并不是必须的没有它也可以只不过运行时间会慢一点。因为st[]的意义就是防止将已经在队列中的点再次入队提升代码运行效率。SPFA算法不能用来求解含有负权回路的图。因为如果有负权回路那么负权回路中的顶点距离源点的距离会不断被更新因此这些顶点也会不断地入队再出队形成一个死循环。因此我们也可以借助SPFA来判断一个图中是否含有负权回路我一会在后面会写到的
拓展
利用SPFA来判断途中是否含有负权回路先看下面的题。 思路
大致思路和前面SPFA思路差不多就是引入了cnt[]数组cnt[]数组是用来记录各个顶点到达源点的最短距离要经过的顶点的数量如果该顶点i和源点联通的话cnt[i]就不为0如果不连通就一直为0关于cnt[]理解起来可能有些困难一会配合着看代码可能要好理解一些
代码
#includeiostream
#includecstring
#includequeueusing namespace std;
const int N100010;
int n,m;
int e[N],ne[N],h[N],w[N],d[N],st[N],cnt[N],idx;void add(int a,int b,int c)
{e[idx]b,ne[idx]h[a],w[idx]c,h[a]idx;
}bool spfa()
{queueint q;for(int i1;in;i) //一开始将所有顶点压入队列{q.push(i);st[i]1;}d[1]0;while(!q.empty()) //队列不为空{int tq.front();q.pop();st[t]0;for(int ih[t];i!-1;ine[i]) //和之前spfa做法一模一样{int je[i];if(d[j]d[t]w[i]){d[j]d[t]w[i];cnt[j]cnt[t]1; //这个表示源点到顶点j经过cnt[t]1个顶点if(cnt[j]n) //如果经过的顶点大于所有顶点数那么就说明含有负权回路return false;if(!st[j]){st[j]1;q.push(j);}}}}return true; //如果最后可以跳出循环就说明没有负权回路
}int main()
{cinnm;memset(h,-1,sizeof h);memset(d,0x3f,sizeof d);while(m--){int a,b,c;cinabc;add(a,b,c);}if(spfa())coutNoendl;else coutYesendl;return 0;
}说明
一开始一定要保证将所有顶点压入队列因为图可能是不连通的。如果不这样的话存在与源点不联通的负权回路就不会被探测出来具体实例可以看下面这张图。 还有一种更优化的方法判断负权回路由于我目前的实力有限还没有看懂思路想了解的童鞋可以看这位大佬KonaeAkira。 感谢各位童鞋看到这里后面我会持续更新数据结构与算法也希望大家点点赞我们一起进步(❁´◡❁)
