LeetCodeCampsDay59图论part09

47.参加科学大会（第六期模拟笔试）

题目描述

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。

小明的起点是第一个车站，终点是最后一个车站。然而，途中的各个车站之间的道路状况、交通拥堵程度以及可能的自然因素（如天气变化）等不同，这些因素都会影响每条路径的通行时间。

小明希望能选择一条花费时间最少的路线，以确保他能够尽快到达目的地。

输入描述

第一行包含两个正整数，第一个正整数 N 表示一共有 N 个公共汽车站，第二个正整数 M 表示有 M 条公路。

接下来为 M 行，每行包括三个整数，S、E 和 V，代表了从 S 车站可以单向直达 E 车站，并且需要花费 V 单位的时间。

输出描述

输出一个整数，代表小明从起点到终点所花费的最小时间。

输入示例

输出示例

提示信息

能够到达的情况：

如下图所示，起始车站为 1 号车站，终点车站为 7 号车站，绿色路线为最短的路线，路线总长度为 12，则输出 12。

不能到达的情况：

如下图所示，当从起始车站不能到达终点车站时，则输出 -1。

数据范围：

1 <= N <= 500;
1 <= M <= 5000;

邻接表

邻接表的，我来给大家画一个图：

图中邻接表表示：

节点1 指向节点3 和节点5
节点2 指向节点4、节点3、节点5
节点3 指向节点4
节点4 指向节点1

dijkstra（堆优化版）思路

在第一个版本的实现思路中，我们提到了三部曲：

第一步，选源点到哪个节点近且该节点未被访问过
第二步，该最近节点被标记访问过
第三步，更新非访问节点到源点的距离（即更新minDist数组）

在LeetCodeCampsDay58里的47题目，我已经使用了一个优化的方法，

def main():
    n, m = map(int, input().split())

    from collections import defaultdict
    graph = [[float('inf')] * (n + 1) for _ in range(n + 1)]
    graphDict = defaultdict(list)

    for _ in range(m):
        s, t, v = map(int, input().split())
        graph[s][t] = v
        graphDict[s].append(t)

    visited = [0] * (n + 1)
    minDist = [float('inf')] * (n + 1)
    minDist[1] = 0

    parent = [-1] * (n + 1)
    for i in range(n + 1):
        lowest = float('inf')
        node = -1
        for j in range(n + 1):
            if visited[j] == 0 and minDist[j] < lowest:
                lowest = minDist[j]
                node = j
        
        if node == -1:
            break

        visited[node] = 1
				
        # 这里使用了邻接表进行遍历，而不是使用邻接矩阵
        for t in graphDict[node]:
            if visited[t] == 0 and minDist[t] > graph[node][t]:
                minDist[t] = min(graph[node][t] + minDist[node], minDist[t])

    print(minDist[-1] if minDist[-1] != float('inf') else -1)
            
    
if __name__ == "__main__":
    main()

但当时主体还是使用邻接矩阵进行遍历，仅在更新非访问节点到源点的距离时使用了邻接表

其实可以全程只使用邻接表，从而进一步减少一些不必要的遍历

但新的问题来了，使用邻接矩阵遍历时，被遍历的对象是0～n这些节点；若使用邻接表，被遍历对象是什么呢？

这里的邻接表仅记录了所有节点到其它节点的信息，但它并不是一个被遍历对象，所以我们需要构造一个被遍历对象：使用一个数据结构，比如队列，我们不断地从队列里取出被遍历对象。初始化时，先将start起点加入到队列，

开始while循环，弹出一个元素（刚开始只能弹出start），将start标记为已经访问，再更新start的邻接表的其它终点到start的minDist距离，并将这些终点添加到队列中，最后，需要对队列再进行排序（按距离从小到大排序），保证队列首一定是距离最小的；随后再进行循环，直到队列里没有其它元素

所以这里使用了“邻接表+队列”来优化遍历

那，是否有哪种数据结构可以自动排序呢？

堆！而且直接把边（带权值）加入到 小顶堆（利用堆来自动排序），那么每次我们从堆顶取出边自然就是距离源点最近的节点所在的边。

那，如何创建本题目需要的邻接表呢？我之前使用的邻接表，仅包含了起点和对应的终点们，如何将每个起点到终点的权值也添加进去？

可以创建一个数据结构，代码如下

class Edge:
    def __init__(self, t, v):
        self.t = t
        self.v = v

def main():
    n, m = map(int, input().split())

    graph = [[] for _ in range(n + 1)]

    for _ in range(m):
        s, t, v = map(int, input().split())
        graph[s].append(Edge(t, v))

代码对应的示意图如下

节点1 指向节点3 权值为 1
节点1 指向节点5 权值为 2
节点2 指向节点4 权值为 7
节点2 指向节点3 权值为 6
节点2 指向节点5 权值为 3
节点3 指向节点4 权值为 3
节点5 指向节点1 权值为 10

堆优化代码

时间复杂度：O(MlogM) M 为边的数量
空间复杂度O(N+M)

import heapq

class Edge:
    def __init__(self, t, v):
        self.t = t
        self.v = v

def main():
    n, m = map(int, input().split())

    graph = [[] for _ in range(n + 1)]

    for _ in range(m):
        s, t, v = map(int, input().split())
        graph[s].append(Edge(t, v))

    visited = [0] * (n + 1)
    minDist = [float('inf')] * (n + 1)
    
    # 创建一个小顶堆
    pq = list()
    # 添加初始点，注意这里的初始点的距离为0
    heapq.heappush(pq, (0, 1))
    # 将start节点的距离设置为0
    minDist[1] = 0

    while pq:
      	# 弹出的节点就是离源点最近的
        curDist, curNode = heapq.heappop(pq)
				
        # 将当前节点标记为访问过
        if visited[curNode] == 1:
            continue
        
        visited[curNode] = 1
				
        # 更新非访问节点到源点的距离（这部分代码和之前差不多）
        for edge in graph[curNode]:
            if visited[edge.t] == 0 and curDist + edge.v < minDist[edge.t]:
                minDist[edge.t] = curDist + edge.v
                # 最重要，记录把相邻节点添加到堆中
                heapq.heappush(pq, (minDist[edge.t], edge.t))
        
    print(minDist[-1] if minDist[-1] != float('inf') else -1)
            
    
if __name__ == "__main__":
    main()

堆优化的时间复杂度只和边的数量有关和节点数无关，在优先级队列中放的也是边。

以上代码中，while (!pq.empty()) 里套了 for (Edge edge : grid[cur.first])

for 里遍历的是当前节点 cur 所连接边。

那当前节点cur 所连接的边也是不固定的，这就让大家分不清，这时间复杂度究竟是多少？

其实 for (Edge edge : grid[cur.first]) 里最终的数据走向是给队列里添加边。

那么跳出局部代码，整个队列一定是所有边添加了一次，同时也弹出了一次。

所以边添加一次时间复杂度是 O(M)， while (!pq.empty()) 里每次都要弹出一个边来进行操作，在优先级队列（小顶堆）中弹出一个元素的时间复杂度是 O(logM) ，这是堆排序的时间复杂度。

（当然小顶堆里是添加元素的时候排序，还是取数元素的时候排序，这个无所谓，时间复杂度都是O(M)，总之是一定要排序的，而小顶堆里也不会滞留元素，有多少元素添加一定就有多少元素弹出）

所以该算法整体时间复杂度为 O（MlogM)

网上的不少分析会把 n （节点的数量）算进来，这个分析是有问题的，举一个极端例子，在n 为 10000，且是有一条边的图里，以上代码，大家感觉执行了多少次？

while (!pq.empty()) 中的 pq 存的是边，其实只执行了一次。

所以该算法时间复杂度和节点没有关系。

至于空间复杂度，邻接表是数组 + 链表数组的空间是 N ，有M条边就申请对应多少个链表节点，所以是复杂度是 N + M

94.城市间货物运输 I

题目描述

某国为促进城市间经济交流，决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市，通过道路网络连接，网络中的道路仅允许从某个城市单向通行到另一个城市，不能反向通行。

网络中的道路都有各自的运输成本和政府补贴，道路的权值计算方式为：运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用；权值为负则表示政府的补贴超过了支出的运输成本，实际表现为运输过程中还能赚取一定的收益。

请找出从城市 1 到城市 n 的所有可能路径中，综合政府补贴后的最低运输成本。如果最低运输成本是一个负数，它表示在遵循最优路径的情况下，运输过程中反而能够实现盈利。

城市 1 到城市 n 之间可能会出现没有路径的情况，同时保证道路网络中不存在任何负权回路。

输入描述

第一行包含两个正整数，第一个正整数 n 表示该国一共有 n 个城市，第二个整数 m 表示这些城市中共有 m 条道路。

接下来为 m 行，每行包括三个整数，s、t 和 v，表示 s 号城市运输货物到达 t 号城市，道路权值为 v （单向图）。

输出描述

如果能够从城市 1 到连通到城市 n，请输出一个整数，表示运输成本。如果该整数是负数，则表示实现了盈利。如果从城市 1 没有路径可达城市 n，请输出 “unconnected”。

输入示例

输出示例

提示信息

示例中最佳路径是从 1 -> 2 -> 5 -> 6，路上的权值分别为 1 2 -2，最终的最低运输成本为 1 + 2 + (-2) = 1。

示例 2：

4 2
1 2 -1
3 4 -1

在此示例中，无法找到一条路径从 1 通往 4，所以此时应该输出 “unconnected”。

数据范围：

1 <= n <= 1000；
1 <= m <= 10000;

-100 <= v <= 100;

Bellman-ford算法思路

本题依然是单源最短路问题，求从节点1 到节点n 的最小费用。 但本题不同之处在于边的权值是有负数了。

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

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

我们在 dijkstra朴素版中专门有讲解：为什么有边为负数使用dijkstra就不行了。

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

该算法是由 R.Bellman 和L.Ford 在20世纪50年代末期发明的算法，故称为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] 应为如何取舍。

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

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

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

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

1	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，因为我们要求最小距离，那么还没有计算过的节点默认是一个最大数，这样才能更新最小距离。

对所有边进行第一次松弛：（什么是松弛，在上面我已经详细讲过）

以示例给出的所有边为例：

接下来我们来松弛一遍所有的边。

边：节点5 -> 节点6，权值为-2 ，minDist[5] 还是默认数值max，所以不能基于节点5 去更新节点6，如图：

（在复习一下，minDist[5] 表示起点到节点5的最短距离）

边：节点1 -> 节点2，权值为1 ，minDist[2] > minDist[1] + 1 ，更新 minDist[2] = minDist[1] + 1 = 0 + 1 = 1 ，如图：

边：节点5 -> 节点3，权值为1 ，minDist[5] 还是默认数值max，所以不能基于节点5去更新节点3 如图：

边：节点2 -> 节点5，权值为2 ，minDist[5] > minDist[2] + 2 （经过上面的计算minDist[2]已经不是默认值，而是 1），更新 minDist[5] = minDist[2] + 2 = 1 + 2 = 3 ，如图：

边：节点2 -> 节点4，权值为-3 ，minDist[4] > minDist[2] + (-3)，更新 minDist[4] = minDist[2] + (-3) = 1 + (-3) = -2 ，如图：

边：节点4 -> 节点6，权值为4 ，minDist[6] > minDist[4] + 4，更新 minDist[6] = minDist[4] + 4 = -2 + 4 = 2

边：节点1 -> 节点3，权值为5 ，minDist[3] > minDist[1] + 5，更新 minDist[3] = minDist[1] + 5 = 0 + 5 = 5 ，如图：

以上是对所有边进行一次松弛之后的结果。

那么需要对所有边松弛几次才能得到起点（节点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 次，然后得出得到终点的最短路径

代码

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

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

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

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

def main():
    n, m = map(int, input().split())
    graph = list()

    for _ in range(m):
        s, t, v = map(int, input().split())
        graph.append([s, t, v])

    minDist = [float('inf')] * (n + 1)
    minDist[1] = 0

    for i in range(1, n):
        updated = False
        for edge in graph:
            s, t, v = edge
            if minDist[s] != float('inf') and minDist[s] + v < minDist[t]:
                minDist[t] = minDist[s] + v
                updated = True
        if not updated:
            break
    

    print(minDist[-1] if minDist[-1] != float('inf') else "unconnected")


if __name__ == "__main__":
    main()