图论：最短路相关算法-Dijstra,SPFA and Floyd

Posted on Edited on

Preface

暑假集训用到了最短路的板子但之前的板子没存下来，在加上之前也看的不是很明白，故这里放点笔记；

部分板子目前还未测试过，谨慎使用$$(2023.7.15)$$；

Content

Problem

用链式前向星方式存储一个有权图$$G(V:E)$$，找到点 $$ i,j $$ 之间权值最小的路径长度；

注意：有时题目中的图其实就是树，而树的路径长度用 $$dfs$$ 就好了不需要用这个；

通常包括$$\ Dijstra 算法,SPFA \ and \ Floyd算法$$，其中小心SPFA被卡爆（）；

Solution

$$Dijstra$$ 算法

Notice:

  • 该算法只能处理边正权图的单源最短路问题，但是它的效率十分优秀，一般采用带小根堆优先队列优化（$$ZKW$$线段树!$$Fibonnaci$$堆!）；

  • 时间复杂度为$$O((|V|+|E|)log|V|)$$;

  • 但这个复杂度放在稠密图里可能会被$%$$$hack$$,需要换成邻接矩阵的方式存图，复杂度为$$O(|V|^2)$$,遇到了再补吧；

Proof：

  • 对于每个点$$v$$均维护一个「当前最短距离数组」$$dis[v]$$ 以及「访问数组」$$vis[v] $$,首先将$$dis[u]$$初始化为0，将其他点的距离初始化为无穷，并将所有点初始化为未访问的。记$$e[i]:u-v$$的边权为 $$e[i].w$$。然后进行以下步骤：
    1. 从所有未访问的点中，找出当前距离最小的,并将其标记为已访问的;
    2. 调整所有出边连接但尚未访问的点，转移状态；
    3. 重复1和2步骤，直到所有点都已访问，因为所有边权权值均为正的，所以用之后访问的结点是不能更新已经访问过的结点的（因为贪婪算法下若可以更新的话必定在还在之前就已经更新过了）；
    4. 可以用pre[y]=i维护最短的路径（点边关系）；

Template：

标准版询问单源最短路径

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#define local
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
using namespace std;

const int N=200005;
struct Edge{
    int head;
    int to;
    int nxt;
    int w;
}e[N];
void add(int u,int v,int w,int& cnt,std::vector<int>& head){
    e[cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].head=u,e[cnt].to=v,e[cnt].w=w;
    cnt++;
    return ;
}//链式前向星建图
//*****************************************************************************************//

long long dis[maxn]; 
//int pre[maxn];
const int INF=1000000009;
class Node{//使用Node维护每次要更新的点和距离
public:
    long long distance;
    int position;
    Node(long long a,int b){distance=a;position=b;}
    bool operator >(const Node&obj) const{
        return distance>obj.distance;
    };
};
class cmp{//小根堆比较函数
public:
    bool operator()(Node&a,Node&b)const{
        return a>b;
    }
};
std::priority_queue<Node,std::vector<Node>,cmp> disQ;
void Dijstra(int u,int n,long long (&dis)[maxn],std::vector<int>& head/*,int (&pre)[maxn]*/){
    for(int i=1;i<=n;i++) dis[i]=INF;
    dis[u]=0;
    disQ.push(Node(0,u));//保存用来更新的队列
    bool vis[maxn];
    memset(vis,false,sizeof(vis));//初始化

    while(!disQ.empty()){
        int x=disQ.top().position;
        disQ.pop();
        if(vis[x]) continue; vis[x]=true;//不再对已访问过的位置进行访问
        for(int j=head[x];j!=-1;j=e[j].nxt){
            int y=e[j].to;//遍历当前位置的邻点，并更新它们
            if(dis[y]>dis[x]+e[j].w){
                dis[y]=dis[x]+e[j].w;
                if(!vis[y]) disQ.push(Node(dis[y],y))/*,pre[y]=i*/;
            }
        }
    }
    return ;
}
//****************************************************************************************//

int main ()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int n,m,s;
    std::cin>>n>>m>>s;

    int cnt=0;
    std::vector<int> head;//head[u],头为u的当前最晚出现的边标号
    head.resize(n+1,-1);
    for(int i=0;i<m;i++){
        int u,v,w;
        std::cin>>u>>v>>w;
        add(u,v,w,cnt,head);
    }
    //memset(pre,0,sizeof(pre));
    Dijstra(s,n,dis,head);
    for(int i=1;i<=n;i++){
        if(i!=1) printf(" ");
        std::cout<<dis[i];
    }
    return 0;
}

$$Floyd$$ 算法

Notice

  • $$Floyd$$ 算法是基于最朴素的动态规划的思想，求出全局上的任意两点的最短路问题，可以处理负边权的情况；
  • 我们知道对于图$$G$$ 中存在负权值环的话，沿着这个环一直前进是不会得到最短路的，$$Floyd$$ 算法也无法处理这类的问题；
  • 在一些加了若干限制的最短路问题中，往往都要回归到朴素的$$Floyd$$算法来；

Proof

考虑对每个$$k$$值，「$$i$$到$$j$$ 的路径只允许经过标号不大于$$k$$的点」中最短路径长度$$dis[i][j]$$，明显$$k=n$$是我们所求问题的答案；

  • 初始$$k=0$$，所欲值都是正无穷；

  • 递归的说，对于已有的$$k-1 $$允许的最短路径，新的最短路径要么经过$$k$$,要么维持不变；

  • 状态转移方程为
    $$
    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]),for\ all\ (i,j)s
    $$

  • 时间复杂度为$$O(|V|^3)$$;

Template:

弱化版单源最短路径，不是正解，只有70分

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
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
const int maxn=10005;
const int N=500005;

long long dis[maxn][maxn]; 
const long long INF= (1<<31)-1;
void Floyd(int n,long long (&dis)[maxn][maxn]){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dis[i][j]=std::min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
    return ;
}
int main ()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int n,m,s;
    std::cin>>n>>m>>s;

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dis[i][j]= INF;
        }
    }
    for(int i=0;i<m;i++){
        int u,v,w;
        std::cin>>u>>v>>w;
        dis[u][v]=std::min(dis[u][v],w*1LL);//可能由重边
    }
    
    Floyd(n,dis);
    for(int i=1;i<=n;i++){
        if(i!=1) printf(" ");
        std::cout<<((i!=s)?dis[s][i]:0);
    }
    return 0;
}

$$SPFA$$ 算法

Notice:

  • 对于一般的带权图，不同于正权图的$$relax$$操作每次取出最小的$$dis$$来进行下一步，边权有负数是不保证正确性的，所以我们维护一个普通的队列就行了，这也是$$SPFA$$经常得卡爆的地方，构造数据可以欺骗算法进入冗余的分支，使得队列的进出和$$relax$$多了很多不必要的操作；
  • 这个算法本质是$$Bellmon-Ford$$算法的局部优化，复杂度为$$O(|V||E|)$$；
  • 所以说没必要仔细解释$$Bellmon$$算法对全局的$$n-1$$次$$relax$$操作了，卡$$SPFA$$的一定卡$$Bellmon$$;
  • （保证输入是随机数据）慎用，不要偷懒！因为它已经死了；

Template:

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
68
69
70
71
72
73
74
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
const int maxn=100005;

const int N=500005;
struct Edge{
    int head;
    int to;
    int nxt;
    int w;
}e[N];
void add(int u,int v,int w,int& cnt,std::vector<int>& head){
    e[cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].head=u,e[cnt].to=v,e[cnt].w=w;
    cnt++;
    return ;
}
//******************************************************************************//
const long long INF=(1<<31)-1;
long long dis[maxn];
void SPFA(int s,int n,long long (&dis)[maxn],std::vector<int> &head){
    for(int i=1;i<=n;i++) dis[i]=INF;
    dis[s]=0;
    bool vis[maxn];
    memset(vis,false,sizeof(vis));

    std::queue<int> disQ;
    disQ.push(s);
    while(!disQ.empty()){
        int x=disQ.front();
        disQ.pop();
        vis[x]=false;
        for(int i=head[x];i!=-1;i=e[i].nxt){
            int y=e[i].to;
            if(dis[y]>dis[x]+e[i].w){
                dis[y]=dis[x]+e[i].w;
                if(!vis[y]){
                    vis[y]=true;
                    disQ.push(y);
                }
            }
        }
    }
}
//*************************************************************************************//
int main ()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int n,m,s;
    std::cin>>n>>m>>s;

    int cnt=0;
    std::vector<int> head;//head[u],头为u的当前最晚出现的边标号
    head.resize(n+1,-1);
    for(int i=0;i<m;i++){
        int u,v,w;
        std::cin>>u>>v>>w;
        add(u,v,w,cnt,head);
    }
    //memset(pre,0,sizeof(pre));
    SPFA(s,n,dis,head);
    for(int i=1;i<=n;i++){
        if(i!=1) printf(" ");
        std::cout<<dis[i];
    }
    return 0;
}

Example

暂时没有；

洛谷P3385 【模板】负环

洛谷P5909【模板】Johnson 全源最短路

Remark

还是多整理一些模板少打比赛吧，太坐牢了，怎么写那么快的啊；

学校的专题等一波题解发下来吧，真的不知道里面是什么毒瘤数据；