在图G中，假设 v i v_{i} vi和 v j v_{j} vj为图中的两个极点，那么 v i v_{i} vi到 v j v_{j} vj路径上所颠末边的权值之和就称为带权路径⻓度。
由于 v i v_{i} vi到 v j v_{j} vj的路径可能有多条，将带权路径⻓度最短的那条路径称为最短路径。
最短路⼀般分为两类：
- 单源最短路，即图中⼀个极点到其它各极点的最短路径。
- 多源最短路，即图中每对极点间的最短路径
常规版dijkstra算法
Dijkstra算法是基于贪⼼思想的单源最短路算法，求解的是"⾮负权图"上单源最短路径
常规版dijkstra算法流程：
- 准备⼯作：
- 创建⼀个⻓度为 n 的 dist 数组，此中 dist 表⽰从出发点到 i 结点的最短路；
- 创建⼀个⻓度为 n 的 bool 数组 st ，此中 st 表⽰ i 点是否已经确定了最短路。
- 初始化： dist[1] = 0 ，其余结点的 dist 值为⽆穷⼤，表⽰还没有找到最短路。
- 重复：在所有没有确定最短路的点中，找出最短路⻓度最⼩的点 u 。打上确定最短路的标记，然后对 u 的出边进⾏松弛操纵；
- 重复上述操纵，直到所有点的最短路都确定
P3371 【模板】单源最短路径（弱化版） - 洛谷
- #include <bits/stdc++.h>
- using namespace std;
- typedef pair<int, int> PII;
- typedef long long LL;
- const int N = 1e4 + 10, INF = 2147483647;
- int n, m, s;
- vector<PII> edges[N];
- LL dist[N];
- bool st[N];
- void dijkstra()
- {
- //初始化
- for (int i = 0; i <= n; i++) dist[i] = INF;
- dist[s] = 0;
- for (int i = 1; i < n; i++)
- {
- //找出没有确定最短路的点中，当前最短路最小的点
- int a = 0;
- for (int j = 1; j <= n; j++)
- if (!st[j] && dist[j] < dist[a])
- a = j;
- //打上标记，松弛
- st[a] = true;
- for (auto& t : edges[a])
- {
- int b = t.first, c = t.second;
- if (dist[a] + c < dist[b])
- {
- dist[b] = dist[a] + c;
- }
- }
- }
- for (int i = 1; i <= n; i++) cout << dist[i] << " ";
- }
- int main()
- {
- ios::sync_with_stdio(false);
- cin.tie(0);
- cin >> n >> m >> s;
- for (int i = 1; i <= m; i++)
- {
- int u, v, w; cin >> u >> v >> w;
- edges[u].push_back({v, w});
- }
- dijkstra();
- return 0;
- }
在常规版的根本上，⽤优先级队列去维护待确定最短路的结点。
堆优化版的dijkstra算法流程：
- 准备⼯作：
- 创建⼀个⻓度为 n 的 dist 数组，此中 dist 表⽰从出发点到 i 结点的最短路；
- 创建⼀个⻓度为 n 的 bool 数组 st ，此中 st 表⽰ i 点是否已经确定了最短路；
- 创建⼀个⼩根堆，维护更新后的结点。（也就是需要确定最短路的结点）
- 初始化： dist[1] = 0 ，然后将 {0, s} 加到堆⾥；其余结点的 dist 值为⽆穷⼤，表⽰还没有找到最短路。
- 重复：弹出堆顶元素，假如该元素已经标记过，就跳过；假如没有标记过，打上标记，进⾏松弛操纵。
- 重复上述操纵，直到堆⾥⾯没有元素为⽌
P4779 【模板】单源最短路径（标准版） - 洛谷
- #include <bits/stdc++.h>
- using namespace std;
- typedef pair<int, int> PII;
- const int N = 1e5 + 10;
- int n, m, s;
- vector<PII> edges[N];
- int dist[N];
- bool st[N];
- priority_queue<PII, vector<PII>, greater<PII>> heap;
- void dijkstra()
- {
- //初始化
- memset(dist, 0x3f, sizeof dist);
- dist[s] = 0;
- heap.push({0, s});
- while (heap.size())
- {
- auto t = heap.top(); heap.pop();
- int a = t.second;
- if (st[a]) continue;
- st[a] = true;
-
- for (auto& x : edges[a])
- {
- int b = x.first, c = x.second;
- if (dist[a] + c < dist[b])
- {
- dist[b] = dist[a] + c;
- heap.push({dist[b], b});
- }
- }
- }
- for (int i = 1; i <= n; i++) cout << dist[i] << " ";
- }
- int main()
- {
- ios::sync_with_stdio(false);
- cin.tie(0);
- cin >> n >> m >> s;
- for (int i = 1; i <= m; i++)
- {
- int a, b, c; cin >> a >> b >> c;
- edges[a].push_back({b, c});
- }
- dijkstra();
-
- return 0;
- }
Bellman‒Ford算法(之后简称BF算法)是⼀种基于松弛操纵的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进⾏判定。
算法核⼼思想：不断尝试对图上每⼀条边进⾏松弛，直到所有的点都⽆法松弛为⽌
Bellman‒Ford算法流程：
- 准备⼯作：
- 创建⼀个⻓度为 n 的 dist 数组，此中 dist 表⽰从出发点到 i 结点的最短路。
- 初始化： dist[1] = 0 ，其余结点的 dist 值为⽆穷⼤，表⽰还没有找到最短路。
- 重复：每次都对所有的边进⾏⼀次松弛操纵。
- 重复上述操纵，直到所有边都不需要松弛操纵为⽌
最多重复多少轮松弛操纵？
在最短路存在的情况下，由于⼀次松弛操纵会使最短路的边数⾄少增长1，⽽最短路的边数最多为n-1。因此整个算法最多执⾏轮松弛操纵n-1轮。故总时间复杂度为O(nm)
- #include <bits/stdc++.h>
- using namespace std;
- typedef pair<int, int> PII;
- typedef long long LL;
- const int N = 1e4 + 10, INF = 2147483647;
- int n, m, s;
- vector<PII> edges[N];
- LL dist[N];
- void bf()
- {
- //初始化
- for (int i = 0; i <= n; i++) dist[i] = INF;
- dist[s] = 0;
- bool flg = false;
- for (int i = 1; i < n; i++)
- {
- flg = false;
-
- for (int u = 1; u <= n; u++)
- {
- if (dist[u] == INF) continue;
- for (auto& t : edges[u])
- {
- int v = t.first, w = t.second;
- if (dist[u] + w < dist[v])
- {
- dist[v] = dist[u] + w;
- flg = true;
- }
- }
- }
- if (flg == false) break;
- }
- for (int i = 1; i <= n; i++) cout << dist[i] << " ";
- }
- int main()
- {
- ios::sync_with_stdio(false);
- cin.tie(0);
- cin >> n >> m >> s;
- for (int i = 1; i <= m; i++)
- {
- int a, b, c; cin >> a >> b >> c;
- edges[a].push_back({b, c});
- }
- bf();
- return 0;
- }
spfa即Shortest Path Faster Algorithm，本质是⽤队列对BF算法做优化。
在BF算法中，很多时候我们并不需要那么多⽆⽤的松弛操纵：
- 只有上⼀次被松弛的结点，它的出边，才有可能引起下⼀次的松弛操纵；
- 因此，假如⽤队列来维护"哪些结点可能会引起松弛操纵"，就能只访问必要的边了，时间复杂度就能低落。
spfa算法流程：
- 准备⼯作：
- 创建⼀个⻓度为 n 的 dist 数组，此中 dist 表⽰从出发点到 i 结点的最短路；
- 创建⼀个⻓度为 n 的 bool 数组 st ，此中 st 表⽰ i 点是否已经在队列中。
- 初始化：标记 dist[1] = 0 ，同时 1 ⼊队；其余结点的 dist 值为⽆穷⼤，表⽰还没有找到最短路。
- 重复：每次拿出队头元素 u ，去掉在队列中的标记，同时对 u 所有相连的点 v 进⾏松弛操纵。
假如结点 v 被松弛，那就放进队列中。
- 重复上述操纵，直到队列中没有结点为⽌。
注意注意注意：
固然在⼤多数情况下spfa跑得很快，但其最坏情况下的时间复杂度为O(nm) 。将其卡到这个复杂度也是不难的，所以在没有负权边时最好使⽤Dijkstra算法。
- #include <bits/stdc++.h>
- using namespace std;
- typedef pair<int, int> PII;
- typedef long long LL;
- const int N = 1e4 + 10, INF = 2147483647;
- int n, m, s;
- vector<PII> edges[N];
- LL dist[N];
- bool st[N]; //标记哪些节点在队列中
- void spfa()
- {
- //初始化
- for (int i = 0; i <= n; i++) dist[i] = INF;
- queue<int> q;
- q.push(s);
- dist[s] = 0;
- st[s] = true;
- while (q.size())
- {
- auto a = q.front(); q.pop();
- st[a] = false;
- for (auto& t : edges[a])
- {
- int b = t.first, c = t.second;
- if (dist[a] + c < dist[b])
- {
- dist[b] = dist[a] + c;
- if (!st[b])
- {
- q.push(b);
- st[b] = true;
- }
- }
- }
- }
- for (int i = 1; i <= n; i++) cout << dist[i] << " ";
- }
- int main()
- {
- ios::sync_with_stdio(false);
- cin.tie(0);
- cin >> n >> m >> s;
- for (int i = 1; i <= m; i++)
- {
- int a, b, c; cin >> a >> b >> c;
- edges[a].push_back({b, c});
- }
- spfa();
- return 0;
- }
|
