Bellman-Ford
KellyFrog
·
·
个人记录
\text{Bellman-Ford}
其核心是一种叫做**松弛操作`Relax()`** 的操作，**维护一点到源点的最短路径值**，即**点权值**
`Relax()`有三个参数，`u`，`v`，`w`，即从`u`向`v`进行松弛操作，`w`为$edge(u, v)$的权值
```cpp
void Relax(int u, int v, int w) {
dis[v] = min(dis[v], dis[u] + w);
}
```
$\text{Bellman-Ford}$算法的本质是进行$|u|\times(|v|-1)$次**松弛操作**，有两层循环
```cpp
for(int i = 0; i < n + 1; i++) { //经过i个点（不含起点）到达的个点的最短路径
for(int j = 0; j < G[i].size(); j++) { //遍历每条边
Relax(i, G[i][j], W[i][j]); // G表示vector存边，W表示vector存权值
}
}
```
执行过程图：
对于前i个点，每个点向外松弛，所得到的下一个阶段的点一定是当前最优的
$\text{Bellman-Ford}$的优化算法：[$\text{spfa}$](https://www.luogu.com.cn/blog/ThereMust/post-spfa)