【C++板块提升计划】最短路算法合集
本帖最后由 zhangjinxuan 于 2023-6-13 20:01 编辑最短路算法合集
本贴收集了一些关于求最短路的算法，供大家学习参考，希望大家能够评分支持！
1. bfs
使用搜索法求出最短路，简单高效，但只能求出边权为 1 的最短路。
这个方法可以求出从一个固定的点出发，到任意点的最短路。
void bfs(int u) {
memset(step, 255, sizeof(step));
step = 0;
q = u;
while (rear + 1 != front) {
int f = q;
for (auto i : edges) {
if (step == -1) {
q[++rear] = i;
step = step + 1;
}
}
}
}
时间复杂度：O(n + m)
空间复杂度：O(n + m)
优点：时间复杂度低，空间复杂度低，容易理解。
缺点：只能求出从一点到任意点的最短路，且边权必须为 1，通用性差。
2. Bellman-Ford
主要思想是松弛操作，枚举每一条边，看看能不能根据这个点去更新其他点的最短路，如果可以，则更新。
如果某一次的迭代没有更新任何点，算法结束。
这样可以求出某一点到任一点的最短路，且边权任意。
void bellman_ford(int t) {
for (int i = 1; i <= n; ++i) {
d = 1ll << 60;
}
d] = 0;
bool changed = 1;
while (changed) {
changed = 0;
for (int i = 1; i <= n; ++i) {
if (d == 1LL << 60) continue;
for (auto j : edges) {
if (d + j.l < d) {
d = d + j.l;
changed = 1;
}
}
}
}
}
时间复杂度：O(nm)（存在最短路的请况下）
空间复杂度：O(n + m)
优点：可以求出任意边权的最短路。
缺点：时间复杂度差。
3. Bellman-Ford + SPFA
根据只有被更新过的点才能更新其他点的性质，我们可以对其进行优化。
void solve(int x) {
memset(vis, 0, sizeof(vis));
vis = 1;
q = x;
memset(d, 127, sizeof(d));
d = 0;
while (front <= rear) {
int x = q;
vis = 0;
for (auto i : eeddges) {
if (d + i.l < d) {
d = d + i.l;
if (!vis) {
vis = 1;
q[++rear] = i.to;
}
}
}
}
}
时间复杂度：O(nm)（存在最短路的请况下）
空间复杂度：O(n + m)
优点：相比于裸的 Bellman-Ford，能提升效率。
缺点：在一定情况，算法也会退化到 O(nm)
4. Floyd
前提是使用邻接矩阵存图（记为 d），这种算法就可以求出任意一点到任意一点的最短路。
memset(d, 127, sizeof(d));
for (int k = 1; k <= n; ++k) for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j)
d = min(d, (d + d));
3 行搞定最短路{:10_279:}
这里感觉优点 DP，主要思路就是记 f 为当前迭代的最短路，i 为起点，j 为终点，k 是代表 i ~ j 的最短路中可以经过 1~k 的点。
这时就有两种选择，一是经过 k，二是不经过 k，若经过 k，就是 d[ i] + d。
时间复杂度：O(n^3)
空间复杂度：O(n^3)
优点：容易理解。
缺点：很慢，只在特殊题目中出现。
5. Floyd + 状态压缩
k 这一个状态其实可以省去。
memset(d, 127, sizeof(d));
for (int k = 1; k <= n; ++k) for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j)
d = min(d, (d + d));
时间复杂度：O(n^3)
空间复杂度：O(n^2)
优点：容易理解，空间复杂度低。
缺点：很慢，只在特殊题目中出现。
6. Dijkstra + 堆优化
使用贪心，在 Bellman-Ford 做了很多优化，省去了很多次的松弛操作，主要是每一次选取距离最小的点来更新其他的点。
void dijkstra(int s) {
memset(d, 127, sizeof(d));
d = 0;
q.clear();
for (int i = 1; i <= n; ++i) {
q.insert({i, d});
}
while (!q.empty()) {
Info fx = *q.begin();
q.erase(fx);
for (auto i : edges) {
if (d + i.d < d) {
q.erase({i.to, d});;
d = d + i.d;
q.insert({i.to, d});
}
}
}
}
时间复杂度：O((n + m) log n)
空间复杂度：O(n + m)
优点：时间复杂度和空间复杂度都很优秀，最常用的最短路算法。
缺点：只能求出固定一点到任意一点的最短里，不利于理解。
如果大家还有什么最短路算法，欢迎回帖分享~ 下次能不能屏蔽我……（算法恐惧症、C++恐惧症患者）
https://fishc.com.cn/home.php?mod=space&do=friend&view=blacklist 本帖最后由 zhangjinxuan 于 2023-6-14 18:43 编辑
歌者文明清理员 发表于 2023-6-13 19:31
下次能不能屏蔽我……（算法恐惧症、C++恐惧症患者）
https://fishc.com.cn/home.php?mod=space&do=friend ...
{:10_277:} 歌者文明清理员 发表于 2023-6-13 19:31
下次能不能屏蔽我……（算法恐惧症、C++恐惧症患者）
https://fishc.com.cn/home.php?mod=space&do=friend ...
{:10_277:} 靠，全不会 喜欢用bfs{:10_256:}
页:
[1]