AI summary
type
status
date
slug
summary
category
tags
icon
password

Dijkstra 算法

先看代码：
优先级队列中最多装 V 个节点，对优先级队列的操作次数和 E 成正比。时间复杂度为： 。
其实是类似贪心加广搜加动归，大致思路是这样的：
先把内层的，最靠近起点的最短路径确定好，然后通过已知的最短路径做中继点，更新其外层节点的现有最短路径，这里的内外层其实是根据离起点的距离分的。
就是说要到 1000m 外的一个地方，中间很多休息区，我要贪心地走每一步，即保证我一定是通过最短路径走到前导节点。到目标点的路径长度随着前导节点的变化不断变短，直至最短。
过程如下图所示：
notion image

Bellman-Ford 算法

大家应该听过 Bellman-Ford 算法，这个算法是一种更通用的最短路径算法，因为它可以处理带有负权重边的图，同时可以检测是否有负权重环。
返回从起点到所有节点的最短路径距离。如果图中存在负权重环，则返回 None。
算法的时间复杂度为 。

练习题

743. 网络延迟时间

有 n 个网络节点，标记为 1 到 n。
给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。
现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
让你求所有节点都收到信号的时间，你把所谓的传递时间看做距离，实际上就是问你「从节点 k 到其他所有节点的最短路径中，最长的那条最短路径距离是多少」，说白了就是让你算从节点 k 出发到其他所有节点的最短路径，就是标准的 Dijkstra 算法。
在用 Dijkstra 之前，别忘了要满足一些条件，加权有向图，没有负权重边，OK，可以用 Dijkstra 算法计算最短路径，直接套用算法框架：

1631. 最小体力消耗路径

你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。
一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。
请你返回从左上角走到右下角的最小 体力消耗值 。
notion image
我们常见的二维矩阵题目，如果让你从左上角走到右下角，比较简单的题一般都会限制你只能向右或向下走，但这道题可没有限制哦，你可以上下左右随便走，只要路径的「体力消耗」最小就行。
如果你把二维数组中每个 (x, y) 坐标看做一个节点，它的上下左右坐标就是相邻节点，它对应的值和相邻坐标对应的值之差的绝对值就是题目说的「体力消耗」，你就可以理解为边的权重。
这样一想，是不是就在让你以左上角坐标为起点，以右下角坐标为终点，计算起点到终点的最短路径？Dijkstra 算法是不是可以做到？
只不过，这道题中评判一条路径是长还是短的标准不再是路径经过的权重总和，而是路径经过的权重最大值。
明白这一点，再想一下使用 Dijkstra 算法的前提，加权有向图，没有负权重边，求最短路径，OK，可以使用，咱们来套框架。
你看，稍微改一改代码模板，这道题就解决了。

1514. 概率最大的路径

给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，其中 edges[i] = [a, b] 表示连接节点 a 和 b 的一条无向边，且该边遍历成功的概率为 succProb[i] 。
指定两个节点分别作为起点 start 和终点 end ，请你找出从起点到终点成功概率最大的路径，并返回其成功概率。
如果不存在从 start 到 end 的路径，请 返回 0 。只要答案与标准答案的误差不超过 1e-5 ，就会被视作正确答案。
我说这题一看就是 Dijkstra 算法，但聪明的你肯定会反驳我：
  1. 这题给的是无向图，也可以用 Dijkstra 算法吗？
  1. 更重要的是，Dijkstra 算法计算的是最短路径，计算的是最小值，这题让你计算最大概率是一个最大值，怎么可能用 Dijkstra 算法呢？
问得好！
首先关于有向图和无向图，无向图本质上可以认为是「双向图」，从而转化成有向图。
重点说说最大值和最小值这个问题，其实 Dijkstra 和很多最优化算法一样，计算的是「最优值」，这个最优值可能是最大值，也可能是最小值。
标准 Dijkstra 算法是计算最短路径的，但你有想过为什么 Dijkstra 算法不允许存在负权重边么？
因为 Dijkstra 计算最短路径的正确性依赖一个前提：路径中每增加一条边，路径的总权重就会增加。
这个前提的数学证明大家有兴趣可以自己搜索一下，我这里只说结论，其实你把这个结论反过来也是 OK 的：
如果你想计算最长路径，路径中每增加一条边，路径的总权重就会减少，要是能够满足这个条件，也可以用 Dijkstra 算法。
你看这道题是不是符合这个条件？边和边之间是乘法关系，每条边的概率都是小于 1 的，所以肯定会越乘越小。
只不过，这道题的解法要把优先级队列的排序顺序反过来，一些 if 大小判断也要反过来，我们直接看解法代码吧：
注意一下正负号的问题，prob 保存的都是正的概率值，pq 里存的是概率值的相反数，因为默认最小堆，而这里需要最大堆。