最短路算法
最短路算法分为两大类:
1.单源最短路,常用算法有:
(1) dijkstra,只有所有边的权值为正时才可以使用。在稠密图上的时间复杂度是 O(n2),稀疏图上的时间复杂度是 O(mlogn)。
(2) spfa,不论边权是正的还是负的,都可以做。算法平均时间复杂度是 O(km),k 是常数。 强烈推荐该算法。
2.多源最短路,一般用floyd算法。代码很短,三重循环,时间复杂度是 O(n3)。
算法模板
我们以 poj2387 Til the Cows Come Home 题目为例,给出上述所有算法的模板。
题目大意
给一张无向图,n 个点 m 条边,求从1号点到 n 号点的最短路径。
输入中可能包含重边。
dijkstra算法 O(n2)
最裸的dijkstra算法,不用堆优化。每次暴力循环找距离最近的点。
只能处理边权为正数的问题。
图用邻接矩阵存储。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 1010, M = 2000010, INF = 1000000000; int n, m; int g[N][N], dist[N]; // g[][]存储图的邻接矩阵, dist[]表示每个点到起点的距离 bool st[N]; // 存储每个点的最短距离是否已确定 void dijkstra() { for (int i = 1; i <= n; i++) dist[i] = INF; dist[1] = 0; for (int i = 0; i < n; i++) { int id, mind = INF; for (int j = 1; j <= n; j++) if (!st[j] && dist[j] < mind) { mind = dist[j]; id = j; } st[id] = 1; for (int j = 1; j <= n; j++) dist[j] = min(dist[j], dist[id] + g[id][j]); } } int main() { cin >> m >> n; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) g[i][j] = INF; for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; g[a][b] = g[b][a] = min(g[a][b], c); } dijkstra(); cout << dist[n] << endl; return 0; }
dijkstra+heap优化 O(mlogn)
用堆维护所有点到起点的距离。时间复杂度是 O(mlogn)。
这里我们可以手写堆,可以支持对堆中元素的修改操作,堆中元素个数不会超过 n。也可以直接使用STL中的priority_queue,但不能支持对堆中元素的修改,不过我们可以将所有修改过的点直接插入堆中,堆中会有重复元素,但堆中元素总数不会大于 m。
只能处理边权为正数的问题。
图用邻接表存储。
typedef pair<int, int> PII; int n; // 点的数量 int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边 int dist[N]; // 存储所有点到1号点的距离 bool st[N]; // 存储每个点的最短距离是否已确定 // 求1号点到n号点的最短距离,如果不存在,则返回-1 int dijkstra() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; priority_queue<PII, vector<PII>, greater<PII>> heap; heap.push({0, 1}); // first存储距离,second存储节点编号 while (heap.size()) { auto t = heap.top(); heap.pop(); int ver = t.second, distance = t.first; if (st[ver]) continue; st[ver] = true; for (int i = h[ver]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > distance + w[i]) { dist[j] = distance + w[i]; heap.push({dist[j], j}); } } } if (dist[n] == 0x3f3f3f3f) return -1; return dist[n]; }
spfa算法 O(km)
bellman-ford算法的优化版本,可以处理存在负边权的最短路问题。
最坏情况下的时间复杂度是 O(nm),但实践证明spfa算法的运行效率非常高,期望运行时间是 O(km),其中 k 是常数。
但需要注意的是,在网格图中,spfa算法的效率比较低,如果边权为正,则尽量使用 dijkstra 算法。如果说dijkstra是步步回头找最小,那么SPFA就是一点一圈扩散去。每到一个点,就直接枚举和它相连的所有边和点,如果走这条路可以更近,那么就更新那个点的dist。如果那个点不在即将更新的队列里,那就放进去。也就是十分类似于BFS的一种做法。在这种做法下,每个点可能被放进队列多次,但是都是带着更新前面的点的dist 的可能进去的。
图采用邻接表存储。
队列为手写的循环队列。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; const int N = 1010, M = 2000010, INF = 1000000000; int n, m; int dist[N], q[N]; // dist表示每个点到起点的距离, q 是队列 int h[N], e[M], v[M], ne[M], idx; // 邻接表 bool st[N]; // 存储每个点是否在队列中 void add(int a, int b, int c) { e[idx] = b, v[idx] = c, ne[idx] = h[a], h[a] = idx++; } void spfa() { int hh = 0, tt = 0; for (int i = 1; i <= n; i++) dist[i] = INF; dist[1] = 0; q[tt++] = 1, st[1] = 1; while (hh != tt) { int t = q[hh++]; st[t] = 0; if (hh == n) hh = 0; for (int i = h[t]; i != -1; i = ne[i]) if (dist[e[i]] > dist[t] + v[i]) { dist[e[i]] = dist[t] + v[i]; if (!st[e[i]]) { st[e[i]] = 1; q[tt++] = e[i]; if (tt == n) tt = 0; } } } } int main() { memset(h, -1, sizeof h); cin >> m >> n; for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; add(a, b, c); add(b, a, c); } spfa(); cout << dist[n] << endl; return 0; }
用spfa判断是否有负环:
bool spfa()//返回true有负环 { queue<int> q; for(int i = 1; i <= n; i++) { q.push(i); fl[i] = 1; } while(q.size()) { int t = q.front(); q.pop(); fl[t] = 0; for(int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if(dist[j] > dist[t] + w[i])//dist数组值为0只有遇到负数才会更新 { dist[j] = dist[t] + w[i]; cnt[j] = cnt[t] + 1; if(cnt[j] >= n) return true; if(!fl[j]) { fl[j] = 1; q.push(j); } } } } return false; }
dijkstra与SPFA这两种算法的核心都是找到另一条路来更新当前的最短路,但是实现方法不大一样。某种程度上说,dijkstra因为即使是堆优化,优先队列的常数也是很大的,而SPFA在稀疏图下步步发散就可以跑得很快,所以有时SPFA可以比Dijkstra快很多,算法的复杂度可以达到O(km)【k为常数】的级别。但是如果是稠密图的话,SPFA也可以退化到O(nm)。所以两种算法也是各有优势,才能一起存活下来。当然,SPFA也是可以用优先队列优化队列的,实现方法最后就和Dijkstra一样了。
floyd算法 O(n3)
标准弗洛伊德算法,三重循环。循环结束之后 d[i][j] 存储的就是点 i 到点 j 的最短距离。
需要注意循环顺序不能变:第一层枚举中间点,第二层和第三层枚举起点和终点。
由于这道题目的数据范围较大,点数最多有1000个,因此floyd算法会超时。
但我们的目的是给出算法模板哦~
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; const int N = 1010, M = 2000010, INF = 1000000000; int n, m; int d[N][N]; // 存储两点之间的最短距离 int main() { cin >> m >> n; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) d[i][j] = i == j ? 0 : INF; for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; d[a][b] = d[b][a] = min(c, d[a][b]); } // floyd 算法核心 for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); cout << d[1][n] << endl; return 0; }
标签:存储,dist,int,短路,dijkstra,算法,include From: https://www.cnblogs.com/lys-blogs123/p/17056148.html