NO.94十六届蓝桥杯备战|图论基础-单源最短路|常规dijkstra|堆优化dijkstra|bellman-ford|spfa(C++)

在图G中，假设$v_i$和$v_j$为图中的两个顶点，那么$v_i$到$v_j$路径上所经过边的权值之和就称为带权路径⻓度。
由于$v_i$到$v_j$的路径可能有多条，将带权路径⻓度最短的那条路径称为最短路径。
最短路⼀般分为两类：

• 单源最短路，即图中⼀个顶点到其它各顶点的最短路径。
• 多源最短路，即图中每对顶点间的最短路径
  

常规版dijkstra算法

Dijkstra算法是基于贪⼼思想的单源最短路算法，求解的是"⾮负权图"上单源最短路径

常规版dijkstra算法流程：

• 准备⼯作：
  • 创建⼀个⻓度为 n 的 dist 数组，其中 dist[i] 表⽰从起点到 i 结点的最短路；
  • 创建⼀个⻓度为 n 的 bool 数组 st ，其中 st[i] 表⽰ 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算法

在常规版的基础上，⽤优先级队列去维护待确定最短路的结点。
堆优化版的dijkstra算法流程：

• 准备⼯作：
  • 创建⼀个⻓度为 n 的 dist 数组，其中 dist[i] 表⽰从起点到 i 结点的最短路；
  • 创建⼀个⻓度为 n 的 bool 数组 st ，其中 st[i] 表⽰ 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算法

Bellman‒Ford算法(之后简称BF算法)是⼀种基于松弛操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进⾏判断。
算法核⼼思想：不断尝试对图上每⼀条边进⾏松弛，直到所有的点都⽆法松弛为⽌

Bellman‒Ford算法流程：

• 准备⼯作：
  • 创建⼀个⻓度为 n 的 dist 数组，其中 dist[i] 表⽰从起点到 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算法

spfa即Shortest Path Faster Algorithm，本质是⽤队列对BF算法做优化。
在BF算法中，很多时候我们并不需要那么多⽆⽤的松弛操作：

• 只有上⼀次被松弛的结点，它的出边，才有可能引起下⼀次的松弛操作；
• 因此，如果⽤队列来维护"哪些结点可能会引起松弛操作"，就能只访问必要的边了，时间复杂度就能降低。
  spfa算法流程：
• 准备⼯作：
  • 创建⼀个⻓度为 n 的 dist 数组，其中 dist[i] 表⽰从起点到 i 结点的最短路；
  • 创建⼀个⻓度为 n 的 bool 数组 st ，其中 st[i] 表⽰ 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;
}