马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 zhangjinxuan 于 2023-6-13 20:01 编辑
最短路算法合集
本贴收集了一些关于求最短路的算法，供大家学习参考，希望大家能够评分支持！
1. bfs
使用搜索法求出最短路，简单高效，但只能求出边权为 1 的最短路。
这个方法可以求出从一个固定的点出发，到任意点的最短路。
void bfs(int u) {
memset(step, 255, sizeof(step));
step[u] = 0;
q[rear = front = 1] = u;
while (rear + 1 != front) {
int f = q[front++];
for (auto i : edges[f]) {
if (step[i] == -1) {
q[++rear] = i;
step[i] = step[f] + 1;
}
}
}
}
时间复杂度：O(n + m)
空间复杂度：O(n + m)
优点：时间复杂度低，空间复杂度低，容易理解。
缺点：只能求出从一点到任意点的最短路，且边权必须为 1，通用性差。
2. Bellman-Ford
主要思想是松弛操作，枚举每一条边，看看能不能根据这个点去更新其他点的最短路，如果可以，则更新。
如果某一次的迭代没有更新任何点，算法结束。
这样可以求出某一点到任一点的最短路，且边权任意。
void bellman_ford(int t) {
for (int i = 1; i <= n; ++i) {
d[t][i] = 1ll << 60;
}
d[t][a[t]] = 0;
bool changed = 1;
while (changed) {
changed = 0;
for (int i = 1; i <= n; ++i) {
if (d[t][i] == 1LL << 60) continue;
for (auto j : edges[i]) {
if (d[t][i] + j.l < d[t][j.to]) {
d[t][j.to] = d[t][i] + j.l;
changed = 1;
}
}
}
}
}
时间复杂度：O(nm)（存在最短路的请况下）
空间复杂度：O(n + m)
优点：可以求出任意边权的最短路。
缺点：时间复杂度差。
3. Bellman-Ford + SPFA
根据只有被更新过的点才能更新其他点的性质，我们可以对其进行优化。
void solve(int x) {
memset(vis, 0, sizeof(vis));
vis[x] = 1;
q[front = rear = 1] = x;
memset(d, 127, sizeof(d));
d[x] = 0;
while (front <= rear) {
int x = q[front++];
vis[x] = 0;
for (auto i : eeddges[x]) {
if (d[x] + i.l < d[i.to]) {
d[i.to] = d[x] + i.l;
if (!vis[i.to]) {
vis[i.to] = 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[k][i][j] = min(d[k - 1][i][j], (d[k - 1][i][k] + d[k - 1][k][j]));
3 行搞定最短路
这里感觉优点 DP，主要思路就是记 f[k][i ][j] 为当前迭代的最短路，i 为起点，j 为终点，k 是代表 i ~ j 的最短路中可以经过 1~k 的点。
这时就有两种选择，一是经过 k，二是不经过 k，若经过 k，就是 d[ i][k] + d[k][j]。
时间复杂度：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[i][j] = min(d[i][j], (d[i][k] + d[k][j]));
时间复杂度：O(n^3)
空间复杂度：O(n^2)
优点：容易理解，空间复杂度低。
缺点：很慢，只在特殊题目中出现。
6. Dijkstra + 堆优化
使用贪心，在 Bellman-Ford 做了很多优化，省去了很多次的松弛操作，主要是每一次选取距离最小的点来更新其他的点。
void dijkstra(int s) {
memset(d, 127, sizeof(d));
d[s] = 0;
q.clear();
for (int i = 1; i <= n; ++i) {
q.insert({i, d[i]});
}
while (!q.empty()) {
Info fx = *q.begin();
q.erase(fx);
for (auto i : edges[fx.to]) {
if (d[fx.to] + i.d < d[i.to]) {
q.erase({i.to, d[i.to]});;
d[i.to] = d[fx.to] + i.d;
q.insert({i.to, d[i.to]});
}
}
}
}
时间复杂度：O((n + m) log n)
空间复杂度：O(n + m)
优点：时间复杂度和空间复杂度都很优秀，最常用的最短路算法。
缺点：只能求出固定一点到任意一点的最短里，不利于理解。
如果大家还有什么最短路算法，欢迎回帖分享~ | 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2023-6-13 19:24:50
置顶卡
千斤顶
显身卡
发表于 2023-6-13 19:31:34
楼主
