最短路

B3601 最短路问题（Bellman-Ford）

B3601 [图论与代数结构 201] 最短路问题 - 洛谷

这道题就是把每条边扫一遍。

因为边的顺序不知道，所以需要跑 n-1 轮。每一轮把所有边都松一遍，同时用 flag 记录这一轮有没有发生更新——用来判定全局是否最优：如果一整轮扫下来没有任何更新，就说明已经改完了，可以提前退出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define endl '\n'

struct Edge{
    ll u,v,w;
};

const ll maxn=2e9;

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int n,m; cin>>n>>m;

    vector<Edge> e(m);
    for(int i=0;i<m;i++) cin>>e[i].u>>e[i].v>>e[i].w;

    vector<ll> s(n+1,maxn);
    s[1]=0;

    for(int i=1;i<n;i++){
        bool flag=false; //用来判定全局是否最优

        //由于边的顺序不知道所以需要跑n-1轮
        for(auto edge:e){
            ll u=edge.u;
            ll v=edge.v;
            ll w=edge.w;

            if(s[u]!=maxn && s[v]>s[u]+w){
                s[v]=s[u]+w;
                flag=true;
            }
        }

        if(!flag) break;//已经改完了，可以退出
    }

    for(int i=1;i<=n;i++){
        if(s[i]==maxn) cout<<-1<<" ";
        else cout<<s[i]<<" ";
    }

    cout<<endl;

    return 0;
}

相似的题目还有洛谷的 P3371，可以测试自己是不是模板可以掌握。但是 Bellman-Ford 在 3371 没有那么优——Dijkstra 它来了！

P3371 单源最短路径（弱化版）

P3371 【模板】单源最短路径（弱化版） - 洛谷

写法一：Bellman-Ford

同一套模板，把源点从固定的 1 改成读进来的 s。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define endl '\n'

struct Edge{
    ll u,v,w;
};

ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1) ans*=a;
        a*=a;
        b>>=1;
    }

    return ans;
}

const ll maxn=qpow(2,31)-1;

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    ll n,m,s; cin>>n>>m>>s;

    vector<Edge> e(m);
    for(int i=0;i<m;i++) cin>>e[i].u>>e[i].v>>e[i].w;

    vector<ll> dis(n+1,maxn);
    dis[s]=0;

    for(int i=1;i<n;i++){
        bool flag=false;

        for(auto edge:e){
            ll u=edge.u;
            ll v=edge.v;
            ll w=edge.w;

            if(dis[u]!=maxn && dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                flag=true;
            }
        }

        if(!flag) break;
    }

    for(int i=1;i<=n;i++){
        cout<<dis[i]<<" ";
    }
    cout<<endl;

    return 0;
}

写法二：Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define endl '\n'

const ll INF=4e18;

struct Edge{
    ll v,w;
};

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    ll n,m,s; cin>>n>>m>>s;

    vector<vector<Edge>> g(n+1);
    for(int i=0;i<m;i++){
        ll u,v,w; cin>>u>>v>>w;
        g[u].push_back({v,w});
    }

    vector<ll> dis(n+1,INF);
    vector<bool> vis(n+1,false);
    dis[s]=0;
    for(int i=1;i<=n;i++){
        int u=-1;
        for(int j=1;j<=n;j++){
            if(!vis[j] && (u==-1||dis[u]>dis[j])){
                u=j;
            }
        }

        if(u==-1 || dis[u]==INF) break;
        vis[u]=true;

        for(auto edge:g[u]){
            ll v=edge.v;
            ll w=edge.w;

            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
            }
        }
    }

    for(int i=1;i<=n;i++){
        if(dis[i]==INF) cout<<(1LL<<31)-1<<" ";
        else cout<<dis[i]<<" ";
    }

    cout<<endl;
    return 0;
}

代码后面和 Bellman 是一样的，但是前面没有遍历每一个点，而是先去找最近的然后扩散。

总结

  • Bellman-Ford 的本质是”把所有边扫一遍”。因为边的顺序未知，所以要跑 n-1 轮；某一轮如果没有任何更新，说明已经收敛，可以提前 break。
  • Dijkstra 与 Bellman-Ford 的后半段（松弛）是一样的，差别在前半段：Bellman-Ford 每轮遍历所有边，Dijkstra 是每轮先找出一个最近的未访问点，再从它向外扩散。
  • 两题的不可达输出处理不同：B3601 输出 -1，P3371 输出 2^31-1。写模板题的时候容易只改输入输出、忘了这一处。