图论 20. Bellman_ford 算法（可以计算负权值的单源最短路算法）

94. 城市间货物运输 I

代码随想录

卡码网无难度标识

Man! 真的不想学了怎么还有这么多最短路算法要学，我直接抄抄抄

• 思路：（摘录修改自代码随想录，仅摘录思路，模拟部分直接点击上面代码随想录链接详看吧）

  • 思路：

    本题依然是单源最短路问题，求 从 节点1 到节点n 的最小费用。

    但本题不同之处在于 边的权值是有负数了。

    从 节点1 到节点n 的最小费用也可以是负数，费用如果是负数 则表示 运输的过程中 政府补贴大于运输成本。

    在求单源最短路的方法中，使用dijkstra 的话，则要求图中边的权值都为正数。

    本题是经典的带负权值的单源最短路问题，此时就轮到Bellman_ford登场了，接下来我们来详细介绍Bellman_ford 算法 如何解决这类问题。

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

  • 什么叫做松弛，为什么是 n-1 次，那“松弛”这两个字究竟是个啥意思？

    先来说什么是 “松弛”。

    《算法四》里面把这个操作叫做 “放松”， 英文版里叫做 “relax the edge”

    所以大家翻译过来，就是 “放松” 或者 “松弛” 。

    但《算法四》没有具体去讲这个 “放松” 究竟是个啥？ 网上很多题解也没有讲题解里的 “松弛这条边，松弛所有边”等等 里面的 “松弛” 究竟是什么意思？

    这里我给大家举一个例子，每条边有起点、终点和边的权值。例如一条边，节点A 到 节点B 权值为value，如图：

    

    minDist[B] 表示 到达B节点 最小权值，minDist[B] 有哪些状态可以推出来？

    状态一： minDist[A] + value 可以推出 minDist[B]

    状态二： minDist[B]本身就有权值 （可能是其他边链接的节点B 例如节点C，以至于 minDist[B]记录了其他边到minDist[B]的权值）

    minDist[B] 应该如何取舍？

    本题我们要求最小权值，那么 这两个状态我们就取最小的

    if (minDist[B] > minDist[A] + value) minDist[B] = minDist[A] + value
    

    也就是说，如果 通过 A 到 B 这条边可以获得更短的到达B节点的路径，即如果 **​minDist[B] > minDist[A] + value​**​ ，那么我们就更新 **​minDist[B] = minDist[A] + value​​ ，​这个过程就叫做 “松弛**​” 。

  • • 以上讲了这么多，其实都是围绕以下这句代码展开：

      if (minDist[B] > minDist[A] + value) minDist[B] = minDist[A] + value
      

      这句代码就是 Bellman_ford算法的核心操作。

      以上代码也可以这么写：minDist[B] = min(minDist[A] + value, minDist[B])​

      如果大家看过代码随想录的动态规划章节，会发现 无论是背包问题还是子序列问题，这段代码（递推公式）出现频率非常高的。

      其实 Bellman_ford算法 也是采用了动态规划的思想，即：

      将一个问题分解成多个决策阶段，通过状态之间的递归关系最后计算出全局最优解。

      （如果理解不了动态规划的思想也无所谓，理解我上面讲的松弛操作就好）

    • 那么为什么是 n - 1次 松弛呢？

      这里要给大家模拟一遍 Bellman_ford 的算法才行，接下来我们来看看对所有边松弛 n - 1 次的操作是什么样的。

      我们依然使用minDist数组来表达 起点到各个节点的最短距离，例如minDist[3] = 5 表示起点到达节点3 的最小距离为5

      模拟过程

      • 初始化：

        起点为节点1， 起点到起点的距离为0，所以 minDist[1] 初始化为0

        其他节点对应的minDist初始化为max，因为我们要求最小距离，那么还没有计算过的节点 默认是一个最大数，这样才能更新最小距离。

      • 重复n-1轮：

        每一轮都要对边集合中的每一条边进行松弛

        解释：

        模拟过程中有对所有边进行一次松弛的模拟，得到的是对所有边进行一次松弛后的结果。

        那么需要对所有边松弛几次才能得到 起点（节点1） 到终点（节点6）的最短距离呢？

        对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离。

        上面的距离中，我们得到里 起点达到 与起点一条边相邻的节点2 和 节点3 的最短距离，分别是 minDist[2] 和 minDist[3]

        这里有录友疑惑了 minDist[3] = 5，分明不是 起点到达 节点3 的最短距离，节点1 -> 节点2 -> 节点5 -> 节点3 这条路线 距离才是4。

        注意我上面讲的是 对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离，这里 说的是 一条边相连的节点。

        与起点（节点1）一条边相邻的节点，到达节点2 最短距离是 1，到达节点3 最短距离是5。

        而 节点1 -> 节点2 -> 节点5 -> 节点3 这条路线 是 与起点 三条边相连的路线了。

        所以对所有边松弛一次 能得到 与起点 一条边相连的节点最短距离。

        那对所有边松弛两次 可以得到与起点 两条边相连的节点的最短距离。

        那对所有边松弛三次 可以得到与起点 三条边相连的节点的最短距离，这个时候，我们就能得到到达节点3真正的最短距离，也就是 节点1 -> 节点2 -> 节点5 -> 节点3 这条路线。

        那么再回归刚刚的问题，需要对所有边松弛几次才能得到 起点（节点1） 到终点（节点6）的最短距离呢？

        节点数量为n，那么起点到终点，最多是 n-1 条边相连。

        那么无论图是什么样的，边是什么样的顺序，我们对所有边松弛 n-1 次 就一定能得到 起点到达 终点的最短距离。

        其实也同时计算出了，起点 到达 所有节点的最短距离，因为所有节点与起点连接的边数最多也就是 n-1 条边。

    • 截止到这里，Bellman_ford 的核心算法思路，大家就了解的差不多了。

      共有两个关键点。

      • “松弛”究竟是个啥？
      • 为什么要对所有边松弛 n - 1 次 （n为节点个数） ？

      那么Bellman_ford的解题解题过程其实就是对所有边松弛 n-1 次，然后得出得到终点的最短路径。

• • 代码：

    注意加入了一个updated变量，来标记当前轮次松弛是否有minDist的更新。如果没有更新，说明minDist已经收敛，要立刻跳出循环，防止超时

    • 时间复杂度： O(N * E) , N为节点数量，E为图中边的数量
    • 空间复杂度： O(N) ，即 minDist 数组所开辟的空间

    关于空间复杂度，可能有录友疑惑，代码中数组grid不也开辟空间了吗？ 为什么只算minDist数组的空间呢？

    grid数组是用来存图的，这是题目描述中必须要使用的空间，而不是我们算法所使用的空间。

    我们在讲空间复杂度的时候，一般都是说，我们这个算法所用的空间复杂度。

    import sys
    
    class Edge: # 有向边s->t
        def __init__(self, s, t, val):
            self.s = s # 出发点
            self.t = t # 到达点
            self.val = val # 边权重
    
    if __name__ == '__main__':
        lines = sys.stdin.readlines()
        n, m = map(int, lines[0].strip().split()) # n个城市（结点），m条道路（边）
    
        # 创建边集合
        edges = []
        for i in range(1, len(lines)):
            s, t, val = map(int, lines[i].strip().split())
            edges.append(Edge(s, t, val))
    
        # 初始化
        minDist = [float('inf')] * (n + 1) # 结点编号1~n
        minDist[1] = 0 # 起点为结点1，距离自己的距离为0
    
        # n-1轮松弛，每一轮都要对边集合中的每一条边进行松弛
        for i in range(n - 1):
            updated = False # 标记当前轮次松弛是否有minDist的更新
            for edge in edges:
                newDist = minDist[edge.s] + edge.val # 基于s -> t计算起点结点1到t的新距离
                if newDist < minDist[edge.t]: # 松弛当前边（取更小的）
                    minDist[edge.t] = newDist
                    updated = True
            if not updated:  # 若边不再更新，说明minDist收敛，立即停止松弛循环（不加这个标记提前出循环，会导致超时）
                break
    
        if minDist[n] == float('inf'): print("unconnected")
        else: print(minDist[n])