单源最短路,英文是Single Source Shortest Path
,通常缩写为SSSP
。常见的单源最短路算法有Floyd
,Dijkstra
,SPFA
等。
<1> Floyd
算法
Floyd
算法,又称Floyd-Warshall
算法。在严格意义上来说,这种算法其实不是单源最短路,而是多元最短路,即任意两点之间距离最短。
Floyd
算法的思想来自于动态规划(Dynamic Programming
),它的时间复杂度是O(n ^ 3)
,复杂度还是比较高的。
Floyd
算法的实现使用的是邻接矩阵。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 算法代码如下:
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,将较小的元素直接插入队首。代码实现如下:
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 次,即证明有负环。代码如下:
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。代码如下:
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; } |
有些时候,题目中给出的图是无向图,那么我们就需要建双向边。代码如下:
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.
It’s really a great and helpful piece of info. I’m glad that you shared this useful info with us. Please keep us informed like this. Thanks for sharing.