代码随想录算法训练营第60期第六十三天打卡

大家好，我们昨天讲解的是拓扑排序与Dijkstra算法的朴素版，其实我们大致了解了两种算法的代码实现，我们通过上次博客了解到拓扑排序其实是可以判断图里是否存在环，而Dijkstra算法则使用于非负边权最短路的求解，今天我们继续昨天的内容，我们首先要了解的就是Djikstra算法的堆优化版本，这个其实我以前就了解过这个算法，还有一个就是Bellman_ford 算法，这个其实就弥补了Djikstra算法不能求解带负边权的最短路，那么很明显我们今天的主题就是最短路算法了。

第一部分 dijkstra（堆优化版）

这个我们首先要区分我们上次讲过的朴素版，我们就来看看这个算法是如何实现的？其实关于图的存储方式我们以前就有讲解过主要有两种方法，一种是邻接矩阵法还有一种是邻接表法，我们说邻接表法对于稀疏图的存储，只需要存储边，空间利用率高，遍历节点链接情况相对容易，这里我们就使用邻接表来存储图，第一步：选源点到哪个节点近且该节点未被访问过，第二步：该最近节点被标记访问过，第三步：更新非访问节点到源点的距离（即更新minDist数组），其实我们在前面的朴素版的dijkstra算法就有提到过这个三部曲，但在那个版本的算法里这三部曲是套在一个 for 循环里，为什么？因为我们是从节点的角度来解决问题。那么当从边的角度出发，在处理三部曲里的第一步（选源点到哪个节点近且该节点未被访问过）的时候，我们可以不用去遍历所有节点了。而且直接把边（带权值）加入到小顶堆（利用堆来自动排序），那么每次我们从堆顶里取出边自然就是距离源点最近的节点所在的边。这个思路我感觉是非常妙，堆是一种很常用的数据结构，它具备排序的功能，当然可能有的语言默认大根堆，有的默认小根堆，我们这里要使用小根堆，因为我们要寻找的是最短路径，这样我们就不需要两层for循环来寻找最近的节点了。

这样有了大致的思路以后，我们就可以逐渐尝试去写代码，但是代码一开始我们就遇到了麻烦，我们应该如何表示邻接表呢？在vector<list<int>> grid(n + 1); 中就不能使用int了，而是需要一个键值对来存两个数字，一个数表示节点，一个数表示指向该节点的这条边的权值。我们的堆优化版依旧是我们的三部曲，那么三部曲中的第一步（选源点到哪个节点近且该节点未被访问过），我们如何选？我们要选择距离源点近的节点（即：该边的权值最小），所以我们需要一个小顶堆来帮我们对边的权值排序，每次从小顶堆堆顶取边就是权值最小的边。这个写起C++代码来也是很难，后面我会一并给出，接下来的更新过程与我们以前是类似的，我就不多说了，我们直接给出大家代码：

#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <climits>
using namespace std; 
// 小顶堆
class mycomparison {
public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}
};
// 定义一个结构体来表示带权重的边
struct Edge {int to;  // 邻接顶点int val; // 边的权重Edge(int t, int w): to(t), val(w) {}  // 构造函数
};int main() {int n, m, p1, p2, val;cin >> n >> m;vector<list<Edge>> grid(n + 1);for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val; // p1 指向 p2，权值为 valgrid[p1].push_back(Edge(p2, val));}int start = 1;  // 起点int end = n;    // 终点// 存储从源点到每个节点的最短距离std::vector<int> minDist(n + 1, INT_MAX);// 记录顶点是否被访问过std::vector<bool> visited(n + 1, false); // 优先队列中存放 pair<节点，源点到该节点的权值>priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pq;// 初始化队列，源点到源点的距离为0，所以初始为0pq.push(pair<int, int>(start, 0)); minDist[start] = 0;  // 起始点到自身的距离为0while (!pq.empty()) {// 1. 第一步，选源点到哪个节点近且该节点未被访问过 （通过优先级队列来实现）// <节点， 源点到该节点的距离>pair<int, int> cur = pq.top(); pq.pop();if (visited[cur.first]) continue;// 2. 第二步，该最近节点被标记访问过visited[cur.first] = true;// 3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）for (Edge edge : grid[cur.first]) { // 遍历 cur指向的节点，cur指向的节点为 edge// cur指向的节点edge.to，这条边的权值为 edge.valif (!visited[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]) { // 更新minDistminDist[edge.to] = minDist[cur.first] + edge.val;pq.push(pair<int, int>(edge.to, minDist[edge.to]));}}}if (minDist[end] == INT_MAX) cout << -1 << endl; // 不能到达终点else cout << minDist[end] << endl; // 到达终点最短路径
}

这里定义小顶堆要注意，还要注意我们的pair表示的是什么。

第二部分 Bellman_ford 算法

Bellman_ford算法的核心思想是对所有边进行松弛n-1次操作（n为节点数量），从而求得目标最短路，这个相当重要，这个松弛是什么意思，这里可以这样理解：

minDist[B] 表示到达B节点最小权值，minDist[B] 有哪些状态可以推出来？状态一： minDist[A] + value 可以推出 minDist[B] 状态二： minDist[B]本身就有权值（可能是其他边链接的节点B 例如节点C，以至于 minDist[B]记录了其他边到minDist[B]的权值），这样的话minDist[B] 应为如何取舍。本题我们要求最小权值，那么这两个状态我们就取最小的，也就是说，如果通过 A 到 B 这条边可以获得更短的到达B节点的路径，即如果 minDist[B] > minDist[A] + value，那么我们就更新 minDist[B] = minDist[A] + value ，这个过程就叫做 “松弛” 。这个其实不就还是更新最短路径，这个是不是让大家想起我们以前学过的动态规划，动态规划里面不就经常有取最小值的操作。接下来我可以简单给大家模拟一下松弛的操作：首先对所有边松弛一次，相当于计算起点到达与起点一条边相连的节点的最短距离。

大家可以先看一下上面的图，边：节点1 -> 节点2，权值为1 ，minDist[2] > minDist[1] + 1 ，更新 minDist[2] = minDist[1] + 1 = 0 + 1 = 1 ，接下来边：节点2 -> 节点5，权值为2 ，minDist[5] > minDist[2] + 2 （经过上面的计算minDist[2]已经不是默认值，而是 1），更新 minDist[5] = minDist[2] + 2 = 1 + 2 = 3 ，但是节点5 -> 节点3，权值为1 ，minDist[5] 还是默认数值max，所以不能基于节点5去更新节点3 ，后续的都是这样，我就不给大家一一演示了。

最后我们可以尝试给出完整代码：

#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;int main() {int n, m, p1, p2, val;cin >> n >> m;vector<vector<int>> grid;// 将所有边保存起来for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val;// p1 指向 p2，权值为 valgrid.push_back({p1, p2, val});}int start = 1;  // 起点int end = n;    // 终点vector<int> minDist(n + 1 , INT_MAX);minDist[start] = 0;for (int i = 1; i < n; i++) { // 对所有边 松弛 n-1 次for (vector<int> &side : grid) { // 每一次松弛，都是对所有边进行松弛int from = side[0]; // 边的出发点int to = side[1]; // 边的到达点int price = side[2]; // 边的权值// 松弛操作 // minDist[from] != INT_MAX 防止从未计算过的节点出发if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) { minDist[to] = minDist[from] + price;  }}}if (minDist[end] == INT_MAX) cout << "unconnected" << endl; // 不能到达终点else cout << minDist[end] << endl; // 到达终点最短路径}

这就是我们的Bellman_ford算法，大家一刷稍微有一些了解就可以，暂时不必追根究底。