Bellman-Ford求具体方案

Bellman-ford 是一个求最短路径的基于贪心思想的算法，标准代码如下：

CPP

for(int i=1;i<=T-1;i++){
    for(int j=1;j<=C;j++){
        if(dis[e[j].b]>dis[e[j].a]+e[j].f){
            dis[e[j].b]=dis[e[j].a]+e[j].f;
        }
        if(dis[e[j].a]>dis[e[j].b]+e[j].f){
            dis[e[j].a]=dis[e[j].b]+e[j].f;
        }
    }
}

为了求出具体方案，我们可以构建一个

pre

数组，其中

pre_i

表示在最短路径中，

pre_i

的下一个点是

i

。

我们以余博士教编程_酷哥OJ_酷哥爱编程_酷哥创客AI编程_OnlineJudge的第1582题为例，我们可以在dis[e[j].a]=dis[e[j].b]+e[j].f;和}之间和dis[e[j].b]=dis[e[j].a]+e[j].f;和}之间分别添加语句pre[e[j].a]=e[j].b;和pre[e[j].b]=e[j].a;，最后写一个

print

函数就好了。标准代码如下：

CPP

#include<bits/stdc++.h>
using namespace std;
int T,C,Ts,Te;
struct Edge{
    int a,b,f;
}e[7000];
int dis[3000],pre[3000];
void print(int x){
    if(x==Ts){
        cout<<Ts;
        return;
    }
    print(pre[x]);
    cout<<"->"<<x;
}
int main(){
    cin>>T>>C>>Ts>>Te;
    for(int i=1;i<=C;i++){
        cin>>e[i].a>>e[i].b>>e[i].f;
    }
    memset(dis,0x3f,sizeof(dis));
    dis[Ts]=0;
    for(int i=1;i<=T-1;i++){
        for(int j=1;j<=C;j++){
            if(dis[e[j].b]>dis[e[j].a]+e[j].f){
                dis[e[j].b]=dis[e[j].a]+e[j].f;
                pre[e[j].b]=e[j].a;
            }
            if(dis[e[j].a]>dis[e[j].b]+e[j].f){
                dis[e[j].a]=dis[e[j].b]+e[j].f;
                pre[e[j].a]=e[j].b;
            }
        }
    }
    cout<<dis[Te]<<endl;
    print(Te);
    return 0;
}

Bellman-Ford求具体方案

讨论操作

回复

相关推荐

Bellman-Ford求具体方案