学习动机

Bellman-Ford 的核心操作只有一个：松弛。对于权重为 w 的边 u -> v，如果经过 u 的路径更短（dist[u] + w < dist[v]），就更新 dist[v]。对每条边反复执行这个操作。

为什么要学习 Bellman-Ford？

• 负权重：它可以处理 Dijkstra 无法处理的情况，例如权重可能是返利或货币套利收益的情况。
• 检测负环：额外进行一轮松弛，就能发现总权重为负的环。
• 简单：不需要优先队列，只需反复松弛边。

代价是速度：O(V * E)，比 Dijkstra 的 O((V + E) log V) 慢。