当前位置：首页 > article >正文

算法工程师第五十一天（dijkstra（堆优化版）精讲 Bellman_ford 算法精讲）

article 2024/11/14 21:19:17

参考文献代码随想录

一、参加科学大会

题目描述

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

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

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

输入描述

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

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

输出描述

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

输入示例

输出示例

提示信息

能够到达的情况：

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

不能到达的情况：

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

数据范围：

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

堆优化细节
其实思路依然是 dijkstra 三部曲：

第一步，选源点到哪个节点近且该节点未被访问过
第二步，该最近节点被标记访问过
第三步，更新非访问节点到源点的距离（即更新minDist数组）
只不过之前是 通过遍历节点来遍历边，通过两层for循环来寻找距离源点最近节点。 这次我们直接遍历边，且通过堆来对边进行排序，达到直接选择距离源点最近节点。

先来看一下针对这三部曲，如果用 堆来优化。

那么三部曲中的第一步（选源点到哪个节点近且该节点未被访问过），我们如何选？

我们要选择距离源点近的节点（即：该边的权值最小），所以 我们需要一个 小顶堆 来帮我们对边的权值排序，每次从小顶堆堆顶 取边就是权值最小的边。

C++定义小顶堆，可以用优先级队列实现，代码如下：

// 小顶堆
class mycomparison {
public:
    bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
        return lhs.second > rhs.second;
    }
};
// 优先队列中存放 pair<节点编号，源点到该节点的权值> 
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pq;
（pair<int, int>中 第二个int 为什么要存 源点到该节点的权值，因为 这个小顶堆需要按照权值来排序）

有了小顶堆自动对边的权值排序，那我们只需要直接从 堆里取堆顶元素（小顶堆中，最小的权值在上面），就可以取到离源点最近的节点了 （未访问过的节点，不会加到堆里进行排序）

所以三部曲中的第一步，我们不用 for循环去遍历，直接取堆顶元素：

// pair<节点编号，源点到该节点的权值>
pair<int, int> cur = pq.top(); pq.pop();

第二步（该最近节点被标记访问过） 这个就是将 节点做访问标记，和 朴素dijkstra 一样 ，代码如下：

// 2. 第二步，该最近节点被标记访问过
visited[cur.first] = true;

（cur.first 是指取 pair<int, int> 里的第一个int，即节点编号 ）

第三步（更新非访问节点到源点的距离），这里的思路 也是 和朴素dijkstra一样的。

但很多录友对这里是最懵的，主要是因为两点：

没有理解透彻 dijkstra 的思路
没有理解 邻接表的表达方式
我们来回顾一下 朴素dijkstra 在这一步的代码和思路（如果没看过我讲解的朴素版dijkstra，这里会看不懂）


// 3、第三步，更新非访问节点到源点的距离（即更新minDist数组）
for (int v = 1; v <= n; v++) {
    if (!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] + grid[cur][v] < minDist[v]) {
        minDist[v] = minDist[cur] + grid[cur][v];
    }
}
其中 for循环是用来做什么的？ 是为了 找到 节点cur 链接指向了哪些节点，因为使用邻接矩阵的表达方式 所以把所有节点遍历一遍。

而在邻接表中，我们可以以相对高效的方式知道一个节点链接指向哪些节点。

再回顾一下邻接表的构造（数组 + 链表）：



假如 加入的cur 是节点 2， 那么 grid[2] 表示的就是图中第二行链表。 （grid数组的构造我们在 上面 「图的存储」中讲过）

所以在邻接表中，我们要获取 节点cur 链接指向哪些节点，就是遍历 grid[cur节点编号] 这个链表。

这个遍历方式，C++代码如下：

for (Edge edge : grid[cur.first]) 
（如果不知道 Edge 是什么，看上面「图的存储」中邻接表的讲解）

cur.first 就是cur节点编号， 参考上面pair的定义： pair<节点编号，源点到该节点的权值>

接下来就是更新 非访问节点到源点的距离，代码实现和 朴素dijkstra 是一样的，代码如下：

// 3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）
for (Edge edge : grid[cur.first]) { // 遍历 cur指向的节点，cur指向的节点为 edge
    // cur指向的节点edge.to，这条边的权值为 edge.val
    if (!visited[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]) { // 更新minDist
        minDist[edge.to] = minDist[cur.first] + edge.val;
        pq.push(pair<int, int>(edge.to, minDist[edge.to]));
    }
}
但为什么思路一样，有的录友能写出朴素dijkstra，但堆优化这里的逻辑就是写不出来呢？

主要就是因为对邻接表的表达方式不熟悉！

以上代码中，cur 链接指向的节点编号 为 edge.to， 这条边的权值为 edge.val ，如果对这里模糊的就再回顾一下 Edge的定义：

struct Edge {
    int to;  // 邻接顶点
    int val; // 边的权重

    Edge(int t, int w): to(t), val(w) {}  // 构造函数
};
确定该节点没有被访问过，!visited[edge.to] ， 目前 源点到cur.first的最短距离（minDist） + cur.first 到 edge.to 的距离 （edge.val） 是否 小于 minDist已经记录的 源点到 edge.to 的距离 （minDist[edge.to]）

如果是的话，就开始更新操作。

即：

if (!visited[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]) { // 更新minDist
    minDist[edge.to] = minDist[cur.first] + edge.val;
    pq.push(pair<int, int>(edge.to, minDist[edge.to])); // 由于cur节点的加入，而新链接的边，加入到优先级队里中
}

同时，由于cur节点的加入，源点又有可以新链接到的边，将这些边加入到优先级队里中。

以上代码思路 和 朴素版dijkstra 是一样一样的，主要区别是两点：

邻接表的表示方式不同
使用优先级队列（小顶堆）来对新链接的边排序

import heapq

class Edge:
def __init__(self, to, val):
self.to = to # 下一个节点
self.val = val

def dijkstra(n, m, edges, start, end):
grid = [[] for _ in range(n + 1)]

for p1, p2, val in edges:
grid[p1].append(Edge(p2, val))

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

pq = []
heapq.heappush(pq, (0, start)) # 把（0， tart）插入到pq中并且维护小根堆的形式
minDist[start] = 0

while pq:

cur_dist, cur_node = heapq.heappop(pq)

if visited[cur_node]:
continue

visited[cur_node] = True

for edge in grid[cur_node]: # 便利哪些点能够是cur_node的出度
if not visited[edge.to] and cur_dist + edge.val < minDist[edge.to]: # edge.to代表的是当前点到其它的所有点
minDist[edge.to] = cur_dist + edge.val # 跟新对应的值
heapq.heappush(pq, (minDist[edge.to], edge.to))

return -1 if minDist[end] == float('inf') else minDist[end]

# 输入
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
start = 1 # 起点
end = n # 终点

# 运行算法并输出结果
result = dijkstra(n, m, edges, start, end)
print(result)

二、城市间货物运输 I（Bellman_ford 算法精讲）

题目描述

某国为促进城市间经济交流，决定对货物运输提供补贴。共有 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;

本题依然是单源最短路问题，求从节点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] 应为如何取舍。

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

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

1
2

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

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

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

1
2

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

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

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

1
2
3
4
5
6
7

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

边：节点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 次，然后得出得到终点的最短路径。

n, m = map(int, input().split())
grid = []
for _ in range(m):
    grid.append(list(map(int, input().split())))

start = 1
end = n
minDist = [float('inf')] * (n + 1)
minDist[start] = 0
for _ in range(n):
    is_update = False  # 判断当前如果没有进行松弛操作，直接跳出，说明已经达到了最小值
    # 对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离。
    for f, t, p in grid:
        if minDist[f] != float("inf") and minDist[t] > minDist[f] + p:  # t是f的一个终点
            minDist[t] = minDist[f] + p
            is_update = True
    if not is_update:
        break
if minDist[end] == float("inf"):
    print("unconnected")
else:
    print(minDist[end])

查看全文

http://www.kler.cn/a/283802.html