文章目录
前言
一、bellman-ford
二、AcWing 853. 有边数限制的最短路
本题分析：
AC代码
三、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解基础算法：bellmen-ford，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、bellman-ford
计算最短路算法的一种，相较于Dijkstra算法，它可以计算有负权边的最短路，下图来自
ACWing算法基础课，关于Dijkstra算法的详细讲解，见博客：Dijkstra
二、AcWing 853. 有边数限制的最短路
本博客给出本题截图：
本题分析：
这里我们没有中邻接表的方式去存储（当然也可以），而是选择了更加方便简单的结构体
struct { int a, b, w; }eg[N];
核心部分的代码类似于Dijkstra，Dijkstra的讲解见博客：Dijkstra
算法核心：
for (int i = 0; i < k; i ++ ) { memcpy(backup, dist, sizeof dist); for (int j = 0; j < m; j ++ ) { auto t = eg[j]; dist[t.b] = min(dist[t.b], backup[t.a] + t.w); } }
这里有一个小细节那就是我们需要备份一下dist数组，拿例子举例：
我们如果不备份的话，那么1号点到2号点的距离更新成1，紧接着会更新2号点到三号点的距离为1，所以1号点到3号点的距离为2，但是我们只有一次更新的机会，所以我们更新3号点的时候不能用已经更新后的2号点的距离，需要用未更新的2号点的距离，那时候的距离为正无穷，因为正无穷 + 1 > 正无穷，所以我们不会用2号点更新3号点，只能用1号点去更新3号点，这样才是正确的做法
这里还有一个小细节就是输出的时候是：
if (dist[n] > 0x3f3f3f3f / 2) cout << "impossible"; else cout << dist[n];
为什么是dist[n] > 0x3f3f3f3f / 2，原因是因为边权可能为负，所以就算是两个正无穷的边在更新的时候，正无穷和正无穷之间的边权为负，那么另一个正无穷被更新的时候会是正无穷减去一个数，小于0x3f3f3f3f，故我们直接要求dist[n] > 0x3f3f3f3f / 2即可.
AC代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 10010, M = 510; int n, m, k; int dist[M], backup[M]; struct { int a, b, w; }eg[N]; void bellman_ford() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i < k; i ++ ) { memcpy(backup, dist, sizeof dist); for (int j = 0; j < m; j ++ ) { auto t = eg[j]; dist[t.b] = min(dist[t.b], backup[t.a] + t.w); } } } int main() { cin >> n >> m >> k; for (int i = 0; i < m; i ++ ) { int x, y, z; cin >> x >> y >> z; eg[i] = {x, y, z}; } bellman_ford(); if (dist[n] > 0x3f3f3f3f / 2) cout << "impossible"; else cout << dist[n]; return 0; }
三、时间复杂度
关于bellmen-ford算法的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
