SPFA做最短路
博客专区 > 侯禹 的博客 > 博客详情
SPFA做最短路
侯禹 发表于4年前
SPFA做最短路
  • 发表于 4年前
  • 阅读 166
  • 收藏 3
  • 点赞 0
  • 评论 0

【腾讯云】如何购买服务器最划算?>>>   

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define Inf 0x7fffffff
#define MaxV 10000
#define MaxE 10000
using namespace std;
int N,M;      //边数
struct Edge
{
    int to,next,w;
}edge[MaxE];
int size,head[MaxV];
void InsertEdge(int from,int to,int w)
{
    edge[size].to=to;
    edge[size].w = w;
    edge[size].next=head[from];
    head[from]=size++;
}
int dist[MaxV];
int  cot[MaxV];
bool vst[MaxV];
int path[MaxV];
bool spfa(int s)
{
    int i;
    int from,to;
    queue<int> que;
    memset(vst,0,sizeof(vst));
    memset(cot,0,sizeof(cot));
    //memset(dist,Inf,sizeof(dist));
    for(i=0;i<=N;i++)
        path[i]=i,dist[i]=Inf;
    path[s]=0,dist[s]=0;
    que.push(s),vst[s]=1;
    while(!que.empty())
    {
        from=que.front();
        que.pop(),vst[from]=0,cot[from]++;
        if(cot[from]>=N)    return 0;
        for(i=head[from];i+1;i=edge[i].next)
        //当head=-1的时候,停止,证明其没有
        {
            to=edge[i].to;
            if(dist[to]>dist[from]+edge[i].w)
            {
                dist[to]=dist[from]+edge[i].w;
                if(!vst[to])
                    que.push(to),vst[to]=1;
            }
        }
    }
    for(i=1;i<=N;i++)
    printf("dist[%d]   =  %d\n",i,dist[i]);
    return 1;
}
void init()
{
    int from,to,w;
    size=0;
    memset(head,-1,sizeof(head));
    scanf("%d%d",&N,&M);
    for(int i=0;i<M;i++)
    {
        scanf("%d%d%d",&from,&to,&w);
        InsertEdge(from,to,w);
    }
}
int main()
{
    freopen("in.txt","r",stdin);
    init();
    if(!spfa(1))    printf("存在负环回路\n");
    else printf("存在最短路径\n");
    return 0;
}


共有 人打赏支持
粉丝 93
博文 49
码字总数 34362
×
侯禹
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: