Akira的OI(咸鱼)圈

最短路

算法
Word count: 781 / Reading time: 4 min
2018/09/03 Share

SPFA

以源点为起点BFS，对边进行逐一松弛，直至松弛至路径最短。

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define ll long long
#define maxn 1000001
using namespace std;
inline int read()
{
    int l=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        l=(l<<3)+(l<<1)+(ch^'0');
        ch=getchar();
    }
    return w*l;
}
int to[maxn],Next[maxn],head[maxn],wi[maxn],dis[maxn],n,m,s;
queue<int>q;
bool inQ[maxn];
int main()
{
    memset(head,-1,sizeof(head));
    int u,v,w,t=0;
    n=read(),m=read(),s=read();
    for(int i=1;i<=n;i++)
        dis[i]=2147483647;
    for(int i=1;i<=m;i++)
    {
        u=read(),v=read(),w=read();
        wi[t]=w,to[t]=v,Next[t]=head[u],head[u]=t++;
    }
    dis[s]=0;
    q.push(s);
    inQ[s]=true;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        inQ[x]=false;
        for(int i=head[x];i!=-1;i=Next[i])
            if(dis[to[i]]>dis[x]+wi[i])
            {
                dis[to[i]]=dis[x]+wi[i];
                if(!inQ[to[i]])
                {
                    q.push(to[i]);
                    inQ[to[i]]=true;
                }
            }
    }
    for(int i=1;i<=n;i++)
        printf("%d ",dis[i]);
    return 0;
}

dijktra+堆优化

dijktra是每次将离源点最近的点取出，对所有该点出边进行松弛，堆优化则是用堆来储存距离，避免了每次重新排序的重复计算。

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define ll long long
#define maxn 1000001
#define pp pair<int,int>
using namespace std;
inline int read()
{
    int l=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        l=(l<<3)+(l<<1)+(ch^'0');
        ch=getchar();
    }
    return w*l;
}
int n,s,wi[maxn],to[maxn],Next[maxn],head[maxn],dis[maxn];
bool vis[maxn];
priority_queue<pp,vector<pp>,greater<pp> >q;
int main()
{
    int m,u,v,w,t=0;
    memset(head,-1,sizeof(head));
    n=read(),m=read(),s=read();
    for(int i=1;i<=n;i++)
        dis[i]=2147483647;
    for(int i=0;i<m;i++)
    {
        u=read(),v=read(),w=read();
        wi[t]=w,to[t]=v,Next[t]=head[u],head[u]=t++;
    }
    dis[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
        pp u=q.top();
        q.pop();
        int x=u.second;
        if(vis[x])
            continue;
        vis[x]=true;
        for(int i=head[x];i!=-1;i=Next[i])
            if(dis[to[i]]>dis[x]+wi[i])
                dis[to[i]]=dis[x]+wi[i],q.push(make_pair(dis[to[i]],to[i]));
    }
    for(int i=1;i<=n;i++)
        printf("%d ",dis[i]);
    return 0;
}

Floyd

Floyd的本质是动态规划，dis[k][i][j]的意思是以1~k为中间点i→j的最短距离，情况可以分为经过k点和不经过k点，由此我们可以得出状态转移方程dis[k][i][j]=min(dis[k-1][i][j]，dis[k-1][i][k]+dis[k-1][k][j])。我们还可以将dis[k][i][j]直接写成dis[i][j],值得注意的是k循环应放在最外层。

1
2
3
4
5
for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(dis[i][k]+dis[k][j]<dis[i][j])
                dis[i][j]=dis[i][k]+dis[k][j];

原文作者: Akira

原文链接: https://akira-1231.github.io/2018/09/03/最短路/

发表日期: 九月 3日 2018, 2:42:17 下午

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. SPFA
  2. 2. dijktra+堆优化
  3. 3. Floyd
Total : 11
2018
题解 算法 杂记