首页 > 代码库 > SPFA 最短路

SPFA 最短路

2024-09-19 23:15:45   220人阅读

 GeneralLiu

 

最短路

什么意思呢

其实就是字面意思喽

 

解法多样

就只介绍 SPFA 了

 

每次 用一个 "有意义" 的点 更新与之相连点 的 dis 值

(至于 dis[]数组    dis[i] 表示 源点 到 i 的最短 距离  ， dis初始化无穷大)

每次 "有意义" 的更新 就把 被更新点 加入 "有意义点 的 队列" 之中去

(至于 "有意义" 就是 dis 值 变小了，变小了 才有可能 把其他点的 dis 值更新得 更小)

到队列为空时 算法结束 dis 数组 即 源点到各点的最短距离

 

技术分享

 

 可以用此图 参考代码 模拟一下

 

例题

 

洛谷 P2951 [USACO09OPEN]捉迷藏Hide and Seek

 

先求出 dis[] 数组

再遍历 dis[] 数组 找出最远 节点  长度  数量

 

代码

 

#include<bits/stdc++.h>using namespace std;#define N 20004#define M 50004int t=1,s,dis[N],n,m,head[N],to[M<<1],next[M<<1],cnt;bool b[N];queue<int>que; // "有意义"的队列 int read(){ //读入优化     int ans=0,ch=getchar();    for(;!isdigit(ch);ch=getchar());    for(;isdigit(ch);ch=getchar())        ans=ans*10+ch-‘0‘;    return ans;}int main(){    n=read(),m=read();    for(int i=1,x,y;i<=m;i++){        x=read(),y=read();        next[++cnt]=head[x]; // 链式前向星         to[cnt]=y;        head[x]=cnt;        next[++cnt]=head[y];        to[cnt]=x;        head[y]=cnt;    }    memset(dis,127/3,sizeof(dis)); // 置一个很大的数      b[1]=1; // 有意义     dis[1]=0;     que.push(1); //push     for(int u,v;!que.empty();){        u=que.front();        que.pop();        b[u]=0; // 已经取出 变为无意义         for(int j=head[u];j;j=next[j]){            v=to[j];            if(dis[v]>dis[u]+1){ // 是否成功修改                 dis[v]=dis[u]+1;                if(!b[v]){  // 是否在队列中                     b[v]=1;                      que.push(v);                }            }        }    }    for(int i=2;i<=n;i++){ // 找答案         if(dis[t]<dis[i]){            t=i;            s=1;        }        else if(dis[t]==dis[i])s++;    }    printf("%d %d %d",t,dis[t],s);    return 0;}

 

SPFA 最短路


联系
我们