图论 19. dijkstra（堆优化版）
图论 19. dijkstra（堆优化版）
卡码网无难度标识
这。。。感觉不如先摘下来，以后再学吧，感觉笔试面试都不一定考得到（考到就直接认栽吧）
（学的太痛苦了，只想快点结束图论开始hot100和补作业）
-
思路：（摘录修改自代码随想录）
-
思路背景：
上一篇文章给出了朴素版的dijkstra算法（图论 18. dijkstra算法（朴素版）（以及dijkstra与prim的区别）-CSDN博客），该解法的时间复杂度为 O(n^2)，可以看出时间复杂度 只和 n （节点数量）有关系。
如果n很大的话，我们可以换一个角度来优化性能：
即，从边的数量出发。
当 n 很大，边 的数量 也很多的时候 （稠密图） ，那么朴素dijkstra没问题；
但 n 很大，边 的数量 很小的时候 （稀疏图） ，可以换成从边的角度来求最短路（毕竟边的数量少）
有的录友可能会想，n （节点数量）很大，边不就多吗？ 怎么会边的数量少呢？
别忘了，谁也没有规定 节点之间一定要有边连接着，例如有一万个节点，只有一条边，这也是一张图。
-
按照稀疏图的角度来分析本题：
-
图的存储：
创建图时，如果是稀疏图， 相比邻接矩阵，邻接表会更优秀一些；
-
在朴素dijkstra的实现思路中，我们提到了三部曲：
- 第一步，选源点到哪个节点近且该节点未被访问过
- 第二步，该最近节点被标记访问过
- 第三步，更新非访问节点到源点的距离（即更新minDist数组）
-
在朴素dijkstra的代码中，三部曲是套在一个 for 循环里，为什么？
因为我们是从节点的角度来解决问题。
三部曲中第一步（选源点到哪个节点近且该节点未被访问过），这个操作本身需要for循环遍历 minDist 来寻找最近的节点。
同时我们需要 遍历所有 未访问过的节点，所以 我们从 节点角度出发，代码会有两层for循环
-
那么当从 边 的角度出发，
在处理 三部曲里的第一步（选源点到哪个节点近且该节点未被访问过）的时候 ，我们可以不用去遍历所有节点了。
而是 **直接把 边（带权值）加入到 小顶堆（利用堆来自动排序），那么每次我们从 堆顶里 取出 边 自然就是 距离源点最近的节点所在的边。**
这样我们就不需要两层for循环来寻找最近的节点了。
-
-
代码实现要点：
-
图的创建：
用邻接表，邻接表数组存放的元素为，由一至多个边Edge类的实例组成的列表。
Edge类里两个参数：边的入点t，和边的权重val。
例如邻接表数组下标1对应结点1，存放的元素为一个列表，里面有一至多个Edge类的实例edge，edge.t是当前边从结点1出发抵达的入点t，edge.val是当前边的权重
-
堆优化细节：
思路依然是 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 链接指向哪些节点，就是遍历 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 是一样一样的，主要区别是两点：
- 邻接表的表示方式不同
- 使用优先级队列（小顶堆）来对新链接的边排序
-
-
代码随想录C++代码：
堆优化dijkstra完整代码如下：
#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，权值为 val grid[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，所以初始为0 pq.push(pair<int, int>(start, 0)); minDist[start] = 0; // 起始点到自身的距离为0 while (!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.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])); } } } if (minDist[end] == INT_MAX) cout << -1 << endl; // 不能到达终点 else cout << minDist[end] << endl; // 到达终点最短路径 }- 时间复杂度：O(ElogE) E 为边的数量
- 空间复杂度：O(N + E) N 为节点的数量
堆优化的时间复杂度 只和边的数量有关 和节点数无关，在 优先级队列中 放的也是边。
以上代码中，
while (!pq.empty()) 里套了for (Edge edge : grid[cur.first])
for 里 遍历的是 当前节点 cur 所连接边。那 当前节点cur 所连接的边 也是不固定的， 这就让大家分不清，这时间复杂度究竟是多少？
其实
for (Edge edge : grid[cur.first]) 里最终的数据走向 是 给队列里添加边。那么跳出局部代码，整个队列 一定是 所有边添加了一次，同时也弹出了一次。
所以边添加一次时间复杂度是 O(E)，
while (!pq.empty()) 里每次都要弹出一个边来进行操作，在优先级队列（小顶堆）中 弹出一个元素的时间复杂度是 O(logE) ，这是堆排序的时间复杂度。（当然小顶堆里 是 添加元素的时候 排序，还是 取数元素的时候排序，这个无所谓，时间复杂度都是O(E)，总之是一定要排序的，而小顶堆里也不会滞留元素，有多少元素添加 一定就有多少元素弹出）
所以 该算法整体时间复杂度为 O（ElogE)
网上的不少分析 会把 n （节点的数量）算进来，这个分析是有问题的，举一个极端例子，在n 为 10000，且是有一条边的 图里，以上代码，大家感觉执行了多少次？
while (!pq.empty()) 中的 pq 存的是边，其实只执行了一次。所以该算法时间复杂度 和 节点没有关系。
至于空间复杂度，邻接表是 数组 + 链表 数组的空间 是 N ，有E条边 就申请对应多少个链表节点，所以是 复杂度是 N + E
-
-
代码随想录python代码：
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)) 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]: if not visited[edge.to] and cur_dist + edge.val < minDist[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)
更多推荐
28
0- 0
已为社区贡献3条内容
所有评论(0)