Bellman-Ford

佚名 6年前 (2019-04-21) 随笔 1414人围观抢沙发百度已收录

普通写法

#include<iostream>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int main() {
    int dis[10],u[10],v[10],w[10],n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>u[i]>>v[i]>>w[i];
    for(int i=1;i<=n;i++) dis[i]=inf;
    dis[1]=0;
    
    for(int k=1;k<=n-1;k++)
        for(int i=1;i<=m;i++)
            if(dis[v[i]]>dis[u[i]]+w[i])
                dis[v[i]]=dis[u[i]]+w[i];
    //检测有无负权回路 
    int flag=0;
    for(int i=1;i<=m;i++)
        if(dis[v[i]]>dis[u[i]]+w[i]) flag=1;
    if(flag==1) cout<<"有负权回路"<<endl;
     
    for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
    return 0;
}

View Code

队列优化：每次仅对最短路估计值发生变化的顶点松弛

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int inf=0x3f3f3f3f;
int main() {
    int n,m;
    cin>>n>>m;
    int u[8],v[8],w[8];
    int first[6],next[6];
    int dis[6],book[6];//book用来记录哪些点在队列中 
    int que[101],head=1,tail=1; 
    memset(que,0,sizeof(que));
    memset(book,0,sizeof(book));
    for(int i=1;i<=n;i++) dis[i]=inf;
    dis[1]=0;
    for(int i=1;i<=n;i++) first[i]=-1;
    for(int i=1;i<=m;i++) {
        cin>>u[i]>>v[i]>>w[i];
        next[i]=first[u[i]];
        first[u[i]]=i;
    }
    que[tail++]=1;
    book[1]=1;
    while(head<tail) { 
        int k=first[que[head]];  //当前需要处理的队首顶点
        while(k!=-1) { //当前顶点的所有边 
            if(dis[v[k]]>dis[u[k]]+w[k]) {
                dis[v[k]]=dis[u[k]]+w[k];
                if(book[v[k]]==0) { //不在队列中 
                    que[tail++]=v[k];
                    book[v[k]]=1;
                }
            }
            k=next[k];
        }
        //出队 
        book[que[head]]=0;
        head++;
    }
    for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
    return 0;
}