单源最短路径 – bellman_ford算法

如果Dijkstra可以解决所有问题，则不需要其他单源最短路径求解方法。

但是恰恰是Dijkstra出现了问题。

由于Dijkstra是贪心算法，导致如果出现负的权值边，则永远无法被访问。如下所示：

此处可以看出，节点1挑选最短边时，由于贪心，只会选择节点3，从而再也不会访问到-300的边，虽然明显1->2->3是最短。

经典的带负权值的单源最短路径问题，就是大名鼎鼎的Bellman_ford算法的场子了。

Bellman_ford算法的核心思想是 对所有边进行松弛n-1次操作（n为节点数量），从而求得目标最短路。

以下是代码随想录的模拟：

初始状态：

初始边：

第一次松弛后结果：

此时结果为只考虑一阶边的单源最短路径。

第二次松弛结果为考虑二阶边的单源最短路径……

解题思路：

• 1 实现n-1次松弛
• 2 松弛关键：
  • if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price){
    minDist[to] = minDist[from] + price;
    }

具体代码如下：