本文主要介绍了图论中最短路问题的三种算法：Floyd、Dijkstra、SPFA

Floyd

基本信息

定义：多源最短路径算法，通过动态规划求解任意两点间最短距离。如果要让任意两点（例如从顶点 aa 到顶点 bb）之间的路程变短，只能引入第三个点（顶点 kk），并通过这个顶点 kk 中转，即 a->k->b，才可能缩短原来从顶点 aa 到顶点 bb 的路程。

原理：三重循环枚举中转点 k，状态转移方程：dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j])

时间复杂度：O(n3)O(n^3)

算法步骤

由于在图中 没有负环 的情况下（如果存在负环则不存在最短路），任意两点之间的最短路不会走重复的点，因此把 1~n 所有的点都作为中转点更新一遍答案，求得的结果就是所有点对之间的最短路。

例题 - Luogu B3647

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int LEN=105,INF=0x3f;
int graph[LEN][LEN],n,m;
signed main()
{
    cin>>n>>m;
    memset(graph,INF,sizeof(graph));//初始化为任何顶点都没有相连
    for(int i=1;i<=n;i++)  graph[i][i]=0;//自己到自己为 0
    while(m--)
    {
        int u,v,w;
        cin>>u>>v>>w;
        graph[u][v]=graph[v][u]=min(graph[u][v],w);//最小值
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j]);
                //暴力查找第三点 k，以及通过边权求最小值
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(graph[i][j]==INF)  cout<<0<<' ';//没有边相连
            else  cout<<graph[i][j]<<' ';
        }
        cout<<endl;
    }
    return 0;
}

上面这玩意只有 80pts

Dijkstra

基本信息

定义：Dijkstra 算法是求从一个点出发到其他所有点的最短路算法。
主要特点：以起始点为中心向外层层扩展，直到扩展到终点为止。算法要求 所有的边权全部非负。

原理：算法原理：每次找出一个到起点距离最小，且没有使用过的点（由于边权非负，从起点到这个点的最短距离已经确定求出），从这个点出发更新起点到（与这个点相连的点）的距离。

时间复杂度：O(n2)O(n^2)

算法步骤

  1. 初始化 graph[v0]=0 ，出发点 到其他顶点的距离 graph[i]=INF
  2. 经过 nn 次下面的操作，最后得到 v0v_0 到 nn 个顶点的最短距离
    1. 选择一个未被标记的、且 graph[k] 的值是最小的顶点 kk
    2. 标记顶点 kk，即 vis[k]=true
    3. 以 kk 为中间点，修改出发点 v0v_0 到其他未被标记的顶点的 jj 的距离值 graph[j]
  3. 将顶点分为两个集合：已求得（已标记的）最短距离的点集合 1，待求点集合 2
    1. 在集合 2 中找一个到出发点距离最近的顶点 kk： min{dis[k]}min\{dis[k]\}
    2. 把顶点 kk 加到集合 1 中，同时检查集合 2 中的剩余顶点 jj 的 dis[j] 是否经过 kk 后变短，如果变短修改 dis[j]
    if(dis[k]+wait[k][j]<dis[j]) dis[j]=dis[k]+wait[k][j]
    3. 重复步骤 3.1 ，直至集合 2 空为止

例题 - Luogu P3371（但是弱化版）

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>
#define int long long
using namespace std;
const int LEN=1e6+5,INF=pow(2,31)-1;
struct Edge
{
    int to,nxt,weight;
}edge[LEN];
int head[LEN],cnt;
int ans[LEN];
bool vis[LEN];
int m,n,s;
void addedge(int u,int v,int w)
{
    cnt++;
    edge[cnt].to=v;
    edge[cnt].weight=w;
    edge[cnt].nxt=head[u];
    head[u]=cnt;
}
void init()
{
    for(int i=1;i<=n;i++)  ans[i]=INF;
    memset(vis,false,sizeof(vis));
    memset(head,0,sizeof(head));
}
signed main()
{
    cin>>m>>n>>s;
    init();
    ans[s]=0;
    for(int i=1;i<=n;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        addedge(u,v,w);
    }
    int pos=s;
    while(vis[pos]==0)
    {
        int minn=INF;
        vis[pos]=true;
        for(int i=head[pos];i!=0;i=edge[i].nxt)
            if(!vis[edge[i].to]&&ans[edge[i].to]>ans[pos]+edge[i].weight)
                ans[edge[i].to]=ans[pos]+edge[i].weight;
        for(int i=1;i<=m;i++)
        {
            if(ans[i]<minn&&vis[i]==0)
            {
                minn=ans[i];
                pos=i;
            }
        }
    }
    for(int i=1;i<=m;i++)  cout<<ans[i]<<' ';
    return 0;
}

但是，这样的算法太慢了！大部分的时间都浪费在了找点上，需要每次选取 dis[] 中的最小值，所以我们可以用……

堆优化

堆是一种可以在 O(log(n))O(log(n)) 的时间插入数据，O(1)O(1) 的时间删除和查找当前极值（最大或最小值）
那么原来求最小值的 O(n)O(n) 的算法，可以改为使用堆来求最小值，时间复杂度降到 O(log(n))O(log(n)) ，整体复杂度降到 O(n log(n))O(n\ log(n))
对于堆可以用手写的，也可以用 STL 中的优先队列（应该没人想用手写堆吧……）

对于 Dijkstra 的堆优化有两种方法:

  1. 重载运算符
  2. 两元组

例题 - Luogu P4779（但是标准版）

别想把 P3371 的代码交上去，全部 TLE

Solution-1 重载运算符

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int LEN=1e6+5,INF=0x3f;
struct Edge
{
    int to,nxt,weight;
}edge[LEN];
struct Priority
{
    int ans,id;
    bool operator <(const Priority &x)const{return x.ans<ans;}
};
int head[LEN],cnt;
int ans[LEN];
bool vis[LEN];
int m,n,s;
void addedge(int u,int v,int w)
{
    cnt++;
    edge[cnt].to=v;
    edge[cnt].weight=w;
    edge[cnt].nxt=head[u];
    head[u]=cnt;
    return;
}
void init()
{
    memset(ans,INF,sizeof(ans));
    memset(vis,false,sizeof(vis));
    memset(head,0,sizeof(head));
}
signed main()
{
    init();
    cin>>m>>n>>s;
    ans[s]=0;
    for(int i=1;i<=n;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        addedge(u,v,w);
    }
    int u;
    priority_queue<Priority> q;
    q.push((Priority){0,s});
    while(!q.empty())
    {
        Priority tmp=q.top();
        q.pop();
        u=tmp.id;
        if(!vis[u])
        {
            vis[u]=true;
            for(int i=head[u];i;i=edge[i].nxt)
            {
                int v=edge[i].to;
                if(ans[v]>ans[u]+edge[i].weight)
                {
                    ans[v]=ans[u]+edge[i].weight;
                    if(!vis[v])  q.push((Priority){ans[v],v});
                }
            }
        }
    }
    for(int i=1;i<=m;i++)  cout<<ans[i]<<' ';
    return 0;
}

Solution-2 两元组

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
#include<bits/stdc++.h>
#define pii pair<int,int>
#define int long long
using namespace std;
const int LEN=1e6+5,INF=pow(2,31)-1;
struct Edge
{
    int to,nxt,weight;
}edge[LEN];
int head[LEN],cnt;
int ans[LEN];
bool vis[LEN];
int m,n,s;
void addedge(int u,int v,int w)
{
    cnt++;
    edge[cnt].to=v;
    edge[cnt].weight=w;
    edge[cnt].nxt=head[u];
    head[u]=cnt;
}
void init()
{
    for(int i=1;i<=n;i++)  ans[i]=INF;
    memset(vis,false,sizeof(vis));
    memset(head,0,sizeof(head));
}
signed main()
{
    cin>>m>>n>>s;
    init();
    priority_queue<pii,vector<pii>,greater<pii> >q;
    for(int i=1;i<=n;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        addedge(u,v,w);
    }
    ans[s]=0;
    q.push(pii{0,s});
    int u;
    while(!q.empty())
    {
        pii x=q.top();
        q.pop();
        if(vis[x.second])  continue;
        u=x.second;
        vis[u]=true;
        for(int i=head[u];i;i=edge[i].nxt)
        {
            if(ans[edge[i].to]>ans[u]+edge[i].weight)
            {
                ans[edge[i].to]=ans[u]+edge[i].weight;
                q.push(pii(ans[edge[i].to],edge[i].to));
            }
        }
    }
    for(int i=1;i<=m;i++)  cout<<ans[i]<<' ';
    return 0;
}

SPFA

SPFA 是 Bellman-Ford 的一种 队列优化，利用了每个点不会更新次数太多的特点，减少了不必要的多余的计算

基本信息

定义：SPFA 是 Bellman-Ford（解决存在负权边的单源最短路问题） 的一种 队列优化，利用了每个点不会更新次数太多的特点，减少了不必要的多余的计算

SPFA 在形式上和 BFS 很像，但是 BFS 搜完一个点之后就不会重新放回队列了，SPFA 在取出一个点进行处理修改时，后面可能产生更短的路径，于是就再次用来修改其他的顶点。

时间复杂度：O(kE)O(kE)，EE 是边数，kk 是常数，平均值是 22

算法步骤

  1. 初始时将出发点加入队列，每次从队列中取出队头，并对所有和队头相连的顶点进行修改
  2. 若某个相邻的顶点修改成功，则将其入队
  3. 队列为空时，算法结束

实现方法

  1. 建立一个队列，并且将出发点入列，用 dis[i] 记录出发点到其他所有点的最短路径
  2. 执行松弛操作，一次用队列里有的点 uu 去更新所有后继节点 viv_i 的最短路，如果 viv_i 被更新成功且不在队列中，则把 viv_i 加入队列，重复执行直到队列为空
  3. 节点可能多次被更新，可以多次进入队列
    if(dis[u]+w<dis[v]) d[v]=d[u]+w;
  4. 如果 VV 被更新了且队列中不存在，再一次进入队列

例题 - Luogu P3371

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>
#define int long long
using namespace std;
const int LEN=5e5+5,INF=pow(2,31)-1;
struct Edge
{
    int to,nxt,weight;
}edge[2*LEN];
int cnt=0,head[LEN],dis[LEN];
bool vis[LEN];
int n,m,start;
void addedge(int u,int v,int w)
{
    cnt++;
    edge[cnt].to=v;
    edge[cnt].weight=w;
    edge[cnt].nxt=head[u];
    head[u]=cnt;
    return;
}
void SPFA()
{
    queue<int> q;
    dis[start]=0;
    q.push(start);
    vis[start]=true;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        vis[now]=false;
        for(int i=head[now];i;i=edge[i].nxt)
        {
            int to=edge[i].to;
            if(edge[i].weight+dis[now]<=dis[to])
            {
                dis[to]=edge[i].weight+dis[now];
                if(!vis[to])
                {
                    q.push(to);
                    vis[to]=true;
                }
            }
        }
    }
    return;
}
void init()
{
    for(int i=1;i<=n;i++)  dis[i]=INF;
    memset(head,0,sizeof(head));
    return;
}
signed main()
{
    cin>>n>>m>>start;
    init();
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        addedge(u,v,w);
    }
    SPFA();
    for(int i=1;i<=n;i++)  cout<<dis[i]<<' ';
    return 0;
}

有些考试会用数据卡掉 SPFA 导致 TLE，比如 Luogu P4779 会导致 SPFA 算法在 #1,2,3,5,6 TLE
SPFA 在最坏情况下和朴素 Bellman-Ford 几乎没有区别

总结

Floyd 最简单，多源最短路大暴力，O(n3)O(n^3) 复杂度卡死你
Dijkstra 时间短，边权非负要确保，不如写上堆优化，时间降到 O(n log(n))O(n\ log(n))
SPFA 易理解，和 BFS 很类似，某些题目 会卡掉，慎重选择需技巧

被迫回去看链式前向星的笔记了 :(

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

快来参与讨论吧~