我们相距十万光年

晨露正葱茏，来日盛景定无穷

11/8
16:19
ACM-ICPC

单源最短路 SSSP

saruka 撰写 无回复

单源最短路，英文是Single Source Shortest Path，通常缩写为SSSP。常见的单源最短路算法有Floyd,Dijkstra,SPFA等。

<1> Floyd算法

Floyd算法，又称Floyd-Warshall算法。在严格意义上来说，这种算法其实不是单源最短路，而是多元最短路，即任意两点之间距离最短。
Floyd算法的思想来自于动态规划（Dynamic Programming），它的时间复杂度是O(n ^ 3)，复杂度还是比较高的。
Floyd算法的实现使用的是邻接矩阵。C++代码如下：

C++
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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
inline int getint()
{
int r = 0, k = 1;
char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if(c == '-') k = -1;
for(; c >= '0' && c <= '9'; c = getchar())
r = r * 10 + c - '0';
return r * k;
}
 
const int maxn = 1005;
const int INF = 0x3f;
 
int n, m, S, T;
int dis[maxn][maxn];
 
int main(int argc, char const * argv[])
{
ios :: sync_with_stdio(false);
 
n = getint();
m = getint();
S = getint();
T = getint();
 
memset(dis, INF, sizeof(dis));
 
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
dis[i][j] = getint();
}
}
 
for(int k = 1; k <= n; i++)
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(dis[i][j] > dis[i][k] + dis[k][j])
{
dis[i][j] = dis[i][k] + dis[k][j];
}
}
}
}
 
printf("%d\n", dis[S][T]);
 
return 0;
}

<2> SPFA 算法

SPFA 算法的全称是 Shortest Path Faster Algorithm，是由西南交通大学的段凡丁教授提出的算法。该算法的实质是对 Bellman-Ford 算法进行了队列优化。

SPFA 的复杂度理论上是O（nm），但是实测情况下 SPFA 算法的复杂度是 O（RP），还是要谨慎使用。朴素的 SPFA 算法代码如下：

C++
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
92
93
94
95
96
97
98
99
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
 
using namespace std;
 
inline int getint()
{
int r = 0, k = 1;
char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if(c == '-') k = -1;
for(; c >= '0' && c <= '9'; c = getchar())
r = r * 10 + c - '0';
return r * k;
}
 
const int maxn = 100005;
const int INF = 1009999999;
 
struct Edge
{
int next, to, w;
} edge[maxn];
 
int n, m, x, y, z, S, T, cnte;
int dis[maxn], h[maxn];
bool vis[maxn];
 
queue <int> q;
 
void add_edge(int x, int y, int z)
{
edge[++cnte].to = y;
edge[cnte].next = h[x];
edge[cnte].w = z;
h[x] = cnte;
}
 
void SPFA()
{
for(int i = 1; i <= n; i++)
{
dis[i] = INF;
vis[i] = false;
}
 
dis[S] = 0;
q.push(S);
vis[S] = true;
int now;
 
while(!q.empty())
{
now = q.front();
q.pop();
vis[now] = false;
 
for(int i = h[now]; i; i = edge[i].next)
{
if(dis[edge[i].to] > dis[now] + edge[i].w)
{
dis[edge[i].to] = dis[now] + edge[i].w;
if(!vis[edge[i].to])
{
q.push(edge[i].to);
vis[edge[i].to] = true;
}
}
}
}
}
 
int main(int argc, char const * argv[])
{
ios :: sync_with_stdio(false);
 
n = getint();
m = getint();
S = getint();
T = getint();
 
for(int i = 1; i <= m; i++)
{
x = getint();
y = getint();
z = getint();
add_edge(x, y, z);
}
 
SPFA();
 
printf("%d\n", dis[T]);
 
return 0;
}

接下来的这种写法是 SPFA 算法的一种优化策略，叫做 SLF（Small Label First），采用了 STL 中的双端队列 deque，将较小的元素直接插入队首。代码实现如下：

C++
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
92
93
94
95
96
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <deque>
#include <cstring>
 
using namespace std;
 
const int INF = 1009999999;
const int maxn = 100010;
const int maxm = 500010;
 
int n, m, S, T, cnte, x, y, z;
int dis[maxn], h[maxn];
bool vis[maxn];
 
deque <int> q;
 
struct Edge
{
    int next, to, w;
} edge[maxn];
 
inline int getint()
{
int r = 0, k = 1;
char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if(c == '-') k = -1;
for(; c >= '0' && c <= '9'; c = getchar())
r = r * 10 + c - '0';
return r * k;
}
 
void add_edge(int x, int y, int z)
{
    edge[++cnte].to = y;
    edge[cnte],next = h[x];
    edge[cnte].w = z;
    h[x] = cnte;
}
 
void SPFA(int s)
{
    for(int i = 1; i <= n; i++)
    {
        dis[i] = INF;
        vis[i] = false;
    }
 
    dis[s] = 0;
    q.push_front(s);
    vis[s] = true;
    int now;
 
    while(!q.empty())
    {
        now = q.front();
        q.pop_front();
        vis[now] = false;
 
        for(int i = head[now]; i; i = edge[i].next)
        {
            if(dis[edge[i].to] > dis[now] + edge[i].w)
            {
                dis[edge[i].to] = dis[now] + edge[i].w;
                
                if(!vis[edge[i].to])
                {
                    if(!q.empty() || dis[edge[i].to] <= dis[q.front()]) q.push_front(edge[i].to);
                    else q.push_back(edge[i].to);
                    vis[edge[i].to] = true;
                }
            }
        }
    }
}
 
int main(int argc, char const * argv[])
{
    n = getint();
    m = getint();
    S = getint();
    T = getint();
    for(int i = 1; i <= m; i++)
    {
        x = getint();
        y = getint();
        z = getint();
        add_edge(x, y, z);
    }
    SPFA(S);
    printf("%d\n", dis[T]);
    return 0;
}

SPFA 算法很重要的一个用处就是判断图中是否存在有负环，只需要额外开一个数组记录一下某个点进入队列的次数。如果该点进队超过 n 次，即证明有负环。代码如下：

C++
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
int judge[maxn];
void SPFA()
{
for(int i = 1; i <= n; i++)
{
dis[i] = INF;
vis[i] = false;
}
 
dis[S] = 0;
q.push(S);
vis[S] = true;
int now;
 
while(!q.empty())
{
now = q.front();
q.pop();
vis[now] = false;
 
for(int i = h[now]; i; i = edge[i].next)
{
if(dis[edge[i].to] > dis[now] + edge[i].w)
{
dis[edge[i].to] = dis[now] + edge[i].w;
if(!vis[edge[i].to])
{
q.push(edge[i].to);
vis[edge[i].to] = true;
if(++judge[edge[i].to] > n) printf("有负环\n");
}
}
}
}
}

<3> Dijkstra 算法

Dijkstra 算法是解决单源最短路问题的经典算法，也是最稳定的算法，适用于没有负边权的情况，其复杂度为O（n ^ 2）。经过二叉堆（Binary Heap）优化之后，其复杂度可以降为O（（m + n）logn）。据说用斐波那契堆（Fibonacci Heap）优化效果更佳，可以把复杂度降为O（n + mlogm），可惜身为蒟蒻的我并不会写。

下面的代码是 Dijkstra 算法的二叉堆优化写法，二叉堆的实现使用的是 STL 中的优先队列 priority_queue。代码如下：

C++
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
92
93
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
 
using namespace std;
 
inline int getint()
{
int r = 0, k = 1;
char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if(c == '-') k = -1;
for(; c >= '0' && c <= '9'; c = getchar())
r = r * 10 + c - '0';
return r * k;
}
 
const int maxn = 100005;
const int INF = 0x3f;
 
struct Edge
{
int u, v, w;
} edge[maxn];
 
struct HeapNode
{
int d, u;
bool operator < (const HeapNode& rhs) const {
return d > rhs.d;
}
};
 
int n, m, S, T;
int dis[maxn];
bool vis[maxn];
 
vector <int> G[10001];
 
void dijkstra(int s)
{
memset(dis, INF, sizeof(dis));
priority_queue <HeapNode> q;
 
dis[s] = 0;
q.push((HeapNode){0, s});
 
while(!q.empty())
{
HeapNode x = q.top();
q.pop();
int u = x.u;
if(vis[u]) continue;
vis[u] = true;
 
for(int i = 0; i < G[u].size(); i++)
{
Edge& e = edge[G[u][i]];
 
if(dis[e.v] > dis[u] + e.w)
{
dis[e.v] = dis[u] + e.w;
q.push((HeapNode){dis[e.v], e.v});
}
}
}
}
 
int main(int argc, char const * argv[])
{
ios :: sync_with_stdio(false);
 
n = getint();
m = getint();
S = getint();
T = getint();
 
for(int i = 1; i <= n; i++)
{
edge[i].u = getint();
edge[i].v = getint();
edge[i].w = getint();
G[edge[i].u].push_back(i);
}
 
dijkstra(S);
printf("%d\n", dis[T]);
return 0;
}

有些时候，题目中给出的图是无向图，那么我们就需要建双向边。代码如下：

C++
1
2
3
4
5
6
7
8
9
10
11
for(int i = 1; i <= m; i++)
{
edge[i].u = getint();
edge[i].v = getint();
edge[i].w = getint();
edge[i + m].u = edge[i].v;
edge[i + m].v = edge[i].u;
edge[i + m].w = edge[i].w;
G[edge[i].u].push_back(i);
G[edge[i + m].u].push_back(i+m);
}

 

Copyright © 2018 All Rights Reserved.