【C++】图论|最短路问题模板

Toms Project • 发布于: 20小时前 • 信息技术 • 19 阅读

本文主要记录最短路及其相关问题（负权环，最小环等）的代码，方便博主自己快速查找。

最短路，即寻找给定图中点之间的最短路径。

目前存在两大类算法：单源最短路径算法，全源最短路径算法。

单源最短路径算法

顾名思义，用白话说就是每次只求两个点之间的最短路径距离。

Dijkstra 算法

是一种求解单源，非负边权，基于松弛的一种贪心算法。

O(n²) 实现

题目：P3371 【模板】单源最短路径（弱化版）（https://www.luogu.com.cn/problem/P3371）

C++

// Dijkstra O(n^2)
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <climits>

using namespace std;
using pii = pair<int, int>;
vector<vector<pii>> edg;
vector<int> dis, vis;

void dijkstra(int n, int s)
{
	dis[s] = 0;
	for (int i = 1; i <= n; i++)
	{
		int u = 0;
		for (int j = 1; j <= n; j++)
		{
			if (!vis[j] && dis[j] < dis[u]) u = j;
		}
		vis[u] = 1;
		for (auto& i : edg[u])
		{
			if (dis[i.first] > dis[u] + i.second)
			{
				dis[i.first] = dis[u] + i.second;
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, s, a, b, c;
	cin >> n >> m >> s;
	edg.resize(n + 1);
	dis.resize(n + 1, INT_MAX);
	vis.resize(n + 1);
	while (m--)
	{
		cin >> a >> b >> c;
		edg[a].emplace_back(b, c);
	}
	dijkstra(n, s);
	for (int i = 1; i <= n; i++)
	{
		cout << dis[i] << " ";
	}
	cout << endl;
	return 0;
}

O(nlog n) 实现

基于优先队列的优化。

题目：P4779 【模板】单源最短路径（标准版）（https://www.luogu.com.cn/problem/P4779）

C++

// Dijkstra O(mlog m)
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <climits>
#include <queue>

using namespace std;
using pii = pair<int, int>;
vector<vector<pii>> edg;
vector<int> vis, dis;

struct point
{
	int u, dis;
	bool operator > (const point& p) const
	{
		return dis > p.dis;
	}
};

void dijkstra(int n, int s)
{
	priority_queue<point, vector<point>, greater<point>> q;
	dis[s] = 0;
	q.emplace(point{ s,0 });
	while (!q.empty())
	{
		auto top = q.top();
		q.pop();
		if (vis[top.u]) continue;
		vis[top.u] = 1;
		for (auto& i : edg[top.u])
		{
			if (dis[i.first] > dis[top.u] + i.second)
			{
				dis[i.first] = dis[top.u] + i.second;
				q.emplace(point{ i.first,dis[i.first] });
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, s, a, b, c;
	cin >> n >> m >> s;
	edg.resize(n + 1);
	dis.resize(n + 1, INT_MAX);
	vis.resize(n + 1);
	while (m--)
	{
		cin >> a >> b >> c;
		edg[a].emplace_back(b, c);
	}
	dijkstra(n, s);
	for (int i = 1; i <= n; i++)
	{
		cout << dis[i] << " ";
	}
	cout << endl;
	return 0;
}

Bellman–Ford 算法

基于对边的松弛操作的最短路算法。(支持负边权)

即每次选择一系列点更新距离，以此类推。

朴素实现

题目：P3371 【模板】单源最短路径（弱化版）（https://www.luogu.com.cn/problem/P3371）

C++

// Bellman–Ford O(nm)
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <climits>

using namespace std;
using pii = pair<int, int>;
vector<vector<pii>> edg;
vector<int> dis;

bool ford(int n, int s)
{
	dis[s] = 0;
	bool flag = 0;
	for (int i = 1; i <= n; i++)
	{
		flag = 0;
		for (int j = 1; j <= n; j++)
		{
			if (dis[j] == INT_MAX) continue;
			for (auto& v : edg[j])
			{
				if (dis[v.first] > dis[j] + v.second)
				{
					dis[v.first] = dis[j] + v.second;
					flag = 1;
				}
			}
		}
		if (!flag) break;
	}
	return flag;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, s, a, b, c;
	cin >> n >> m >> s;
	edg.resize(n + 1);
	dis.resize(n + 1, INT_MAX);
	while (m--)
	{
		cin >> a >> b >> c;
		edg[a].emplace_back(b, c);
	}
	ford(n, s);
	for (int i = 1; i <= n; i++)
	{
		cout << dis[i] << " ";
	}
	cout << endl;
	return 0;
}

队列优化：SPFA

题目：P3371 【模板】单源最短路径（弱化版）（https://www.luogu.com.cn/problem/P3371）

C++

// SPFA O(km ~ nm)
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <climits>
#include <queue>

using namespace std;
using pii = pair<int, int>;
vector<vector<pii>> edg;
vector<int> dis, vis, cnt;

bool spfa(int n, int s)
{
	queue<int> q;
	dis[s] = 0;
	vis[s] = 1;
	q.emplace(s);
	while (!q.empty())
	{
		auto u = q.front();
		q.pop();
		vis[u] = 0;
		for (auto& v : edg[u])
		{
			if (dis[v.first] > dis[u] + v.second)
			{
				dis[v.first] = dis[u] + v.second;
				cnt[v.first] = cnt[u] + 1;
				if (cnt[v.first] >= n) return 1;
				if (!vis[v.first])
				{
					vis[v.first] = 1;
					q.emplace(v.first);
				}
			}
		}
	}
	return 0;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, s, a, b, c;
	cin >> n >> m >> s;
	edg.resize(n + 1);
	dis.resize(n + 1, INT_MAX);
	vis.resize(n + 1);
	cnt.resize(n + 1);
	while (m--)
	{
		cin >> a >> b >> c;
		edg[a].emplace_back(b, c);
	}
	spfa(n, s);
	for (int i = 1; i <= n; i++)
	{
		cout << dis[i] << " ";
	}
	cout << endl;
	return 0;
}

负环判断

同时，以上两种实现都可以进行负权环的判断，只需修改主函数获取返回值即可。

题目：P3385 【模板】负环（https://www.luogu.com.cn/problem/P3385）

C++

// Bellman–Ford O(nm)
void solve()
{
	int n, m, a, b, c;
	cin >> n >> m;
	edg = vector<vector<pii>>(n + 1);
	dis = vector<int>(n + 1, INT_MAX);
	while (m--)
	{
		cin >> a >> b >> c;
		if (c >= 0)
		{
			edg[a].emplace_back(b, c);
			edg[b].emplace_back(a, c);
		}
		else edg[a].emplace_back(b, c);
	}
	if (ford(n, 1)) cout << "YES" << endl;
	else cout << "NO" << endl;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--) solve();
	return 0;
}

C++

// SPFA O(km ~ nm)
void solve()
{
	int n, m, a, b, c;
	cin >> n >> m;
	edg = vector<vector<pii>>(n + 1);
	dis = vector<int>(n + 1, INT_MAX);
	cnt = vector<int>(n + 1);
	vis = vector<int>(n + 1);
	while (m--)
	{
		cin >> a >> b >> c;
		if (c >= 0)
		{
			edg[a].emplace_back(b, c);
			edg[b].emplace_back(a, c);
		}
		else edg[a].emplace_back(b, c);
	}
	if (spfa(n, 1)) cout << "YES" << endl;
	else cout << "NO" << endl;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--) solve();
	return 0;
}

全源最短路径算法

用人话说就是跑一次算法，求出图中所有点之间的最短路径距离。

Floyd 算法

本质上是一种动态规划算法。

直观的讲，就是找一条两点 i, j 之间的路径，这个路径经过了第三个点 k, 使得绕一下比直达的距离更短（边权和更小）。

1. 求最短路：

题目：B3647 【模板】Floyd（https://www.luogu.com.cn/problem/B3647）

C++

// Floyd O(n^3)
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
constexpr int INF = 1e6;
vector<vector<int>> dis;

void floyd(int n)
{
	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m, a, b, c;
	cin >> n >> m;
	dis = vector<vector<int>>(n + 1, vector<int>(n + 1, INF));
	for (int i = 1; i <= n; i++) dis[i][i] = 0;
	while (m--)
	{
		cin >> a >> b >> c;
		// 处理重复的边权
		dis[a][b] = min(c, dis[a][b]);
		dis[b][a] = min(c, dis[b][a]);
	}
	floyd(n);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cout << dis[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}

2. 求最短路径（具体走的路径）

只需在上面的模板中加入一个记录路径的变量，随后递归输出即可。

C++

// Floyd O(n^3) + 路径记录
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
constexpr int INF = 1e6;
vector<vector<int>> dis, p;

void floyd(int n)
{
	for (int k = 1; k <= n; k++)
	{
		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];
					p[i][j] = k;
				}
			}
		}
	}
}

void path(int i, int j)
{
	if (p[i][j] == 0) return;
	int k = p[i][j];
	path(i, k);
	cout << k << " ";
	path(k, j);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m, a, b, c;
	cin >> n >> m;
	dis = vector<vector<int>>(n + 1, vector<int>(n + 1, INF));
	p.resize(n + 1, vector<int>(n + 1));
	for (int i = 1; i <= n; i++) dis[i][i] = 0;
	while (m--)
	{
		cin >> a >> b >> c;
		// 处理重复的边权
		dis[a][b] = min(c, dis[a][b]);
		dis[b][a] = min(c, dis[b][a]);
	}
	floyd(n);
	path(1, n);
	return 0;
}

3. 求无向图的最小环

基本思路就是利用 Floyd 一层一层加点的特性，每次找所有环中最小的。

题目：P6175 无向图的最小环问题（https://www.luogu.com.cn/problem/P6175）

C++

// Floyd O(n^3) + 最小环
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
constexpr int INF = 1e8;
vector<vector<int>> w, dis;
int ans = INF + 10;

void floyd(int n)
{
	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i < k; i++)
		{
			for (int j = i + 1; j < k; j++)
			{
				ans = min(ans, dis[i][j] + w[i][k] + w[k][j]);
			}
		}
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, a, b, c;
	cin >> n >> m;
	w = vector<vector<int>>(n + 1, vector<int>(n + 1, INF));
	for (int i = 1; i <= n; i++) w[i][i] = 0;
	while (m--)
	{
		cin >> a >> b >> c;
		w[a][b] = min(w[a][b], c);
		w[b][a] = min(w[b][a], c);
	}
	dis = w;
	floyd(n);
	if (ans >= INF) cout << "No solution." << endl;
	else cout << ans << endl;
	return 0;
}

Johnson 算法

把 SPFA 和 Dijkstra 结合起来，并对边权进行改造的，支持负边权的算法。

C++

// Johnson O(nmlog m)
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>

using namespace std;
using ll = long long;
constexpr int INF = 1e9;
using pii = pair<int, int>;
vector<vector<pii>> edg;
vector<int> dis, h, vis, cnt;

bool spfa(int n, int s)
{
	queue<int> q;
	h[s] = 0;
	vis[s] = 1;
	q.emplace(s);
	while (!q.empty())
	{
		auto u = q.front();
		q.pop();
		vis[u] = 0;
		for (auto& v : edg[u])
		{
			if (h[v.first] > h[u] + v.second)
			{
				h[v.first] = h[u] + v.second;
				cnt[v.first] = cnt[u] + 1;
				if (cnt[v.first] >= n) return 1;
				if (!vis[v.first])
				{
					vis[v.first] = 1;
					q.emplace(v.first);
				}
			}
		}
	}
	return 0;
}

struct point
{
	int u, dis;
	bool operator > (const point& p) const
	{
		return dis > p.dis;
	}
};

void dijkstra(int n, int s)
{
	priority_queue<point, vector<point>, greater<point>> q;
	dis[s] = 0;
	q.emplace(point{ s,0 });
	while (!q.empty())
	{
		auto top = q.top();
		q.pop();
		if (vis[top.u]) continue;
		vis[top.u] = 1;
		for (auto& i : edg[top.u])
		{
			if (dis[i.first] > dis[top.u] + i.second)
			{
				dis[i.first] = dis[top.u] + i.second;
				q.emplace(point{ i.first,dis[i.first] });
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, a, b, c;
	cin >> n >> m;
	edg.resize(n + 1);
	vis.resize(n + 1);
	cnt.resize(n + 1);
	h.resize(n + 1, INF);
	while (m--)
	{
		cin >> a >> b >> c;
		edg[a].emplace_back(b, c);
	}
	for (int i = 1; i <= n; i++)
	{
		edg[0].emplace_back(i, 0);
	}
	if (spfa(n + 1, 0))
	{
		cout << "-1" << endl;
		return 0;
	}
	for (int u = 1; u <= n; u++)
	{
		for (auto& v : edg[u])
		{
			v.second += h[u] - h[v.first];
		}
	}
	for (int u = 1; u <= n; u++)
	{
		dis = vector<int>(n + 1, INF);
		vis = vector<int>(n + 1);
		dijkstra(n, u);
		ll ans = 0;
		for (ll v = 1; v <= n; v++)
		{
			if (dis[v] == INF) ans += v * INF;
			else ans += v * (dis[v] + h[v] - h[u]);
		}
		cout << ans << endl;
	}
	return 0;
}

目前有关最短路和其相关问题就这些内容。希望我以后遗忘可以慢一点。。。同时如果这也能帮到你，我很荣幸。真的。。

版权声明：
作者：Toms Project
链接：https://blog.projectoms.com/pages/1648.html
来源：Toms Project 官方博客
文章版权归作者所有，未经允许请勿转载。

THE END

ACM C++CSP Dijkstra Floyd ICPC Java NOI NOIP Python TomsProject 免费图论数据结构最短路竞赛算法蓝桥杯

二维码

打赏

【C++】图论|生成树问题(MST)模板

< <上一篇

【C++】图论|最短路问题模板

下一篇>>

文章目录

关闭

搜索内容

【C++】图论|最短路问题模板

单源最短路径算法

Dijkstra 算法

O(n²) 实现

O(nlog n) 实现

Bellman–Ford 算法

朴素实现

队列优化：SPFA

负环判断

全源最短路径算法

Floyd 算法

Johnson 算法

取消回复

共有 0 条评论

作者信息

近期文章

最新评论

热门文章

标签云