Si_Yue小屋
0%

最短路问题

发表于 分类于

单源点最短路问题

  1. spfa算法(由于比bellman-ford优化了一点点，就不记这个了)
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
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN=1e4+2;
const int INF=0x7fffffff;
int n,m,s;

struct edge{
    int to,w;
};

vector<edge> p[MAXN];

int dis[MAXN],isv[MAXN],cnt[MAXN];
queue<int> q;

void add(int u,int v,int w){
    p[u].push_back({v,w});
}

bool spfa(int n,int s){
    fill_n(dis+1,n,INF);
    dis[s]=0,isv[s]=1;
    q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        isv[u]=0;
        for(auto& [v,w]:p[u]){
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>=n)return false;
                if(!isv[v])q.push(v),isv[v]=1;
            }
        }
    }
    return true;
}

signed main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;++i){
        int u,v,w;cin>>u>>v>>w;
        add(u,v,w);
    }
    auto boolean=spfa(n,s);
    for(int i=1;i<=n;++i){
        cout<<dis[i]<<" ";
    }cout<<endl;
}

spfa算法可以判断过某一个源点是否经过负环。如果要判断全图是否有负环，只需要建立一个超级源点，然后将其与原来图中每一个点相连接，边权设置为0，在用spfa算法处理一下（切记现在点个数为n+1）。

  1. 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
54
55
56
57
#include <bits/stdc++.h>

using namespace std;

const int MAXN=1e4+3;
const int INF=0x7fffffff;

struct node{
    int u,dis;
    bool operator>(const node& _node)const{
        return dis>_node.dis;
    }
};

struct edge{
    int to,w;
};

int n,m,s;
vector<edge> p[MAXN];
priority_queue<node,vector<node>,greater<node>> q;
int dis[MAXN],vis[MAXN];

void add(int u,int v,int w){
    p[u].push_back({v,w});
}

void dijkstra(int n,int s){
    fill_n(dis+1,n,INF);
    dis[s]=0;
    q.push({s,0});
    while(!q.empty()){
        int u=q.top().u;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(auto& [v,w]:p[u]){
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push({v,dis[v]});
            }
        }
    }
}

int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;++i){
        int u,v,w;cin>>u>>v>>w;
        add(u,v,w);
    }
    dijkstra(n,s);
    for(int i=1;i<=n;++i){
        cout<<dis[i]<<" ";
    }cout<<"\n";
    return 0;
}

多源点最短路问题

floid算法

floid算法的思想就是dp，并且这个思想可以求出传递闭包。

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
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
#define int long long
using namespace std;
//跑不过p3371，因为floid算法时间复杂度是O(n^3)
const int MAXN=1e4+2;
const int INF=0x7fffffff;
int n,m,s;

struct edge{
    int to,w;
};

vector<edge> p[MAXN];

int f[MAXN][MAXN];

void add(int u,int v,int w){
    p[u].push_back({v,w});
}

void start(){
    for(int i=1;i<=n;++i){
        f[i][i]=0;
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if(i==j)continue;
            f[i][j]=INF;
        }
    }
    for(int i=1;i<=n;++i){
        for(auto edge:p[i]){
            if(i!=edge.to)
            if(f[i][edge.to])
            f[i][edge.to]=min(f[i][edge.to],edge.w);
            else{
                f[i][edge.to]=edge.w;
            }
        }
    }
}

void floid(){
    for(int k=1;k<=n;++k){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                if(f[i][j]>f[i][k]+f[k][j])f[i][j]=f[i][k]+f[k][j];
            }
        }
    }
}

signed main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;++i){
        int u,v,w;cin>>u>>v>>w;
        add(u,v,w);
    }
    start();
    floid();
    for(int i=1;i<=n;++i){
        cout<<f[s][i]<<" ";
    }cout<<endl;
}

选择性免费过k条路，如何求最短路？

这里要用分层图的思想

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
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>

using namespace std;

const int MAXN=1e4+1;
const int INF=0x3f3f3f3f;

struct node{
    int u,dis,cnt;
    node(int _u,int _dis,int _cnt):u(_u),dis(_dis),cnt(_cnt){}
    bool operator>(const node& other)const{
        return dis>other.dis;
    }
};

struct edge{
    int to,w;
};

int n,m,k;
int s,t;
vector<edge> p[MAXN];
priority_queue<node,vector<node>,greater<node>> pq;
int dis[MAXN][12],vis[MAXN][12];

void add(int u,int v,int w){
    p[u].push_back({v,w});
    p[v].push_back({u,w});
}

void dijkstra(int n,int s){
    memset(dis,0x3f,sizeof(dis));
    dis[s][0]=0;
    pq.push({s,0,0});
    while(!pq.empty()){
        int u=pq.top().u,cnt=pq.top().cnt;
        pq.pop();
        if(vis[u][cnt])continue;
        vis[u][cnt]=1;
        for(auto& [v,w]:p[u]){
            if(cnt<k&&dis[v][cnt+1]>dis[u][cnt]){
                dis[v][cnt+1]=dis[u][cnt];
                pq.push({v,dis[v][cnt+1],cnt+1});
            }
            if(dis[v][cnt]>dis[u][cnt]+w){
                dis[v][cnt]=dis[u][cnt]+w;
                pq.push({v,dis[v][cnt],cnt});
            }
        }
    }
}

int main(){
    cin>>n>>m>>k;
    cin>>s>>t;
    for(int i=1;i<=m;++i){
        int u,v,w;cin>>u>>v>>w;
        add(u,v,w);
    }
    dijkstra(n,s);
    int ans=0x7fffffff;
    for(int i=0;i<=k;++i){
        ans=min(ans,dis[t][i]);
    }
    cout<<ans<<endl;
    return 0;
}

在原来dijkstra算法的基础上增加一维，代表层数，第i层代表的是免费过i次。

那么我们的状态转移方程就是：分别判断是否会更新免费过和收费过的距离dis。

差分约束算法

给出一组包含 \(m\) 个不等式，有 \(n\) 个未知数的形如：

\[ \begin{cases} x_{c_1}-x_{c'_1}\leq y_1 \\x_{c_2}-x_{c'_2} \leq y_2 \\ \cdots\\ x_{c_m} - x_{c'_m}\leq y_m\end{cases}\]

的不等式组，求任意一组满足这个不等式组的解。

这个题的意思就是将\(c'\)向\(c\)建边，权值为\(y\)，看这个图有没有负环。用spfa算法处理即可。

无边图的次短路算法

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
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
//无向图的次短路

using namespace std;

const int MAXN=3e5+12;
const int INF=0x3f3f3f3f;

int n,m;
int dis[MAXN],dis2[MAXN],vis[MAXN];

struct node{
    int u,dis;
    node(int _u,int _dis):u(_u),dis(_dis){}
    bool operator>(const node& other)const{return dis>other.dis;}
};

struct edge{
    int v,w;
};

vector<edge> p[MAXN];
priority_queue<node,vector<node>,greater<node>> pq;

void add(int u,int v,int w){
    p[u].push_back({v,w});
    p[v].push_back({u,w});
}

void dijkstra(int n,int s){
    fill_n(dis+1,n,INF);
    fill_n(dis2+1,n,INF);
    dis[s]=0;
    pq.push({s,0});
    while(!pq.empty()){
        int u=pq.top().u;pq.pop();
        // if(vis[u])continue;
        // vis[u]=1;
        for(auto& [v,w]:p[u]){
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                pq.push({v,dis[v]});
            }
            if(dis[v]<dis[u]+w&&dis2[v]>dis[u]+w){
                dis2[v]=dis[u]+w;
                pq.push({v,dis[v]});
            }
            if(dis2[v]>dis2[u]+w){
                dis2[v]=dis2[u]+w;
            }
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int u,v,w;cin>>u>>v>>w;
        add(u,v,w);
    }
    dijkstra(n,1);
    cout<<dis2[n]<<endl;
    return 0;
}

无向图的次短路比有向图的k短路问题好处理且思想不一样。

这里只需要再维护一个次小值就好了，思想是：在dijkstra算法的基础上，解除重复访问的限制，然后根据以下方法更新

1
2
3
4
5
6
7
8
9
10
11
12
// 比较的时候涉及dis[]就要把该状态压进状态的优先队列
if(dis[v]>dis[u]+w){
    dis[v]=dis[u]+w;
    pq.push({v,dis[v]});
}
if(dis[v]<dis[u]+w&&dis2[v]>dis[u]+w){
    dis2[v]=dis[u]+w;
    pq.push({v,dis[v]});
}
if(dis2[v]>dis2[u]+w){
    dis2[v]=dis2[u]+w;
}