fucking-algorithm
fucking-algorithm copied to clipboard
labuladong
我写了一个模板，把 Dijkstra 算法变成了默写题 :: labuladong的算法小抄
while (!pq.isEmpty()) {
State curState = pq.poll();
int curNodeID = curState.id;
int curDistFromStart = curState.distFromStart;
// 在这里加一个判断就行了，其他代码不用改
if (curNodeID == end) {
return curDistFromStart;
}
if (curDistFromStart > distTo[curNodeID]) {
continue;
}
}
"因为优先级队列自动排序的性质，每次从队列里面拿出来的都是 distFromStart 值最小的，所以当你从队头拿出一个节点，如果发现这个节点就是终点 end，那么 distFromStart 对应的值就是从 start 到 end 的最短距离。"
以上判断好像有问题 例如: a->b->c 权重分别为2,1 , a到c的路径最小距离是3 a->d->e->f->c 权重分别为1, a到c的路径最小距离是4 按照你上边所说, 应该会遍历a->d->e->f->c 这条路径, 拿到的最小路径是4, 是错误的
re: doubleSkinMilk 在你举得例子中 b->c 会先于 f->c 被遍历到，因为distFromStart是一个Priority Queue，而distFromStart[b] < distFromStart[f]
东哥好，大家好。我有个问题没想明白。在第 743 题「网络延迟时间」中，为什么curDistFromStart > distTo[curId]。也就是当前路径长度小于dp table里储存的路径长度时，不去更新distTo[curId]啊。 就是为什么不用写注释掉的那一行。
int[] dijkstra(int start, List<int[]>[] graph){
int[] distTo = new int[graph.length];
Arrays.fill(distTo, Integer.MAX_VALUE);
distTo[start] = 0;
PriorityQueue<State> pq = new PriorityQueue<>(
graph.length, (a,b) ->(a.distFromStart - b.distFromStart)
);
pq.offer(new State(start,0));
while(!pq.isEmpty()){
State curState = pq.poll();
int curId = curState.id;
int curDistFromStart = curState.distFromStart;
if(curDistFromStart > distTo[curId]){
continue;
}else{
// distTo[curId] = curDistFromStart;
for(int[] nextNode : graph[curId]){
int nextId = nextNode[0];
int nextDistFromStart = distTo[curId] + nextNode[1];
if(nextDistFromStart < distTo[nextId]){
distTo[nextId] = nextDistFromStart;
pq.offer(new State(nextId, nextDistFromStart));
}
}
}
}
return distTo;
}
我刚才试了下，加上 distTo[curId] = curDistFromStart;对结果没有影响。我能想明白加上的逻辑，但想不明白为什么去掉后算法还是对的呢？
@YZG112358 "在你举得例子中 b->c 会先于 f->c 被遍历到，因为distFromStart是一个Priority Queue，而distFromStart[b] < distFromStart[f]"，理论上来说f在b后面是没有问题的，关键有可能还没有到b呢f就先到了终点c，我还是很难理解这种思路
@doubleSkinMilk @southrivers 首先有几个算法里的前置条件
- 每一次移动都会导致路径的权重增加，即路径权重大于等于0
- 每次在PriorityQueue里取出的node(i)是已经到达的点，而不是即将到达
- 每次在PriorityQueue里取出的node(i)，不管这个node(i)是不是离目标地最近，至少是从起点到node的路线里最短的
- 接着上一点，相比于node(i), 在PriorityQueue里面的node(j), node(k)等等，他们到达各自当前的点的距离必然是大于等于node(i)的权重
由此可以推断
- 根据(2)和(3)，当PriorityQueue里取出的node(destination)的时候，我们至少得到了一种到达终点的路径path(i)和这条路径的权重weight(i)
- 根据(4)，目前得到的这个路径path(i)的权重weight(i)是小于等于PriorityQueue中其他还没到达终点的路径
- 根据(1)，其他的路径到达终点时因为还有走更多的路，所以必然大于等于他们当前的权重，除非其他的路径也正好到达了终点。所以，其他的备选路径的最终权重大于等于当前权重
- 结合前两点，路径path(i)到达终点的权重小于等于其他路径的最终权重
用公式表达
- 因为PriorityQueue对权重排序
weight(i)<=weight(j),weight(k)...
- 因为path(i)已经到达终点
weight(destination, i)=weight(i)weight(destination, i)<=weight(j),weight(k), ...
- 因为路径权重不为负数，其他路径的最终权重会大于当前权重。除非已经到达终点或者剩余路程权重都是0
weight(j)<=weight(destination, j)weight(k)<=weight(destination, k)- ...
- 根据不等式传递公式
weight(destination, i)=weight(i)<=weight(j),weight(k), ... <=weight(destination, j),weight(destination, k), ...
@JackShang94 在加入PirorityQueue的时候已经更新过了。类似的还有BFS模版里在加入Queue的时候同时加入visited。
for(int[] nextNode : graph[curId]){
int nextId = nextNode[0];
int nextDistFromStart = distTo[curId] + nextNode[1];
if(nextDistFromStart < distTo[nextId]){
//******************************************************
distTo[nextId] = nextDistFromStart;
//******************************************************
pq.offer(new State(nextId, nextDistFromStart));
}
}
@Goolloo,我有相同的疑问，请问为什么这个地方nextDistFromStart = distTo[curId] + nextNode[1];这么更新之后再加入PriorityQueue也是对的呢？这个时候distTo[curId] >= curDistFromStart，不应该先更新distTo[curId] = curDistFromStart吗？
@JackShang94 @XiaoyuZhou-hub 关于你们的疑问， @Goolloo 说的是对的，入队的时候已经。你可以先不考虑 Dijkstra 算法，就考虑 常规 BFS 算法，也是要在入队之前把节点加入 visited 集合，而不是在出队的时候加入 visited 集合。
至于为什么要在入队的时候加入 visited 集合，主要是效率的考量：
由于可能多次访问同一节点（走回头路），所以在一个节点 x 入队之后但还未出队的这段时间窗口里，BFS 算法还可能会访问 x 试图将它加入队列。如果在 x 入队的时候就加入 visited，那么这种情况就不会发生；但如果等 x 出队后才加入 visited，这种情况就会发生，导致队列中存在很多冗余重复的 x，它们不会影响最终结果的正确性，但是会拖慢算法的效率。
Dijkstra 算法作为进阶版的 BFS 算法，也是同样的道理，distTo 数组起到的作用就类似 visited 集合的作用。
@JackShang94 你在那里加代码不会产生任何影响，因为 distTo[curId] 那时候本就等于 curDistFromStart，它们就是上一轮的 distTo[nextId] 和 nextDistFromStart。
进一步，你甚至可以尝试把 distTo[nextId] = nextDistFromStart; 这一句代码去掉，结果应该也是对的，但是效率会大幅下降。这就是我刚说的 BFS 算法中加入 visited 集合的时机的问题了。
@doubleSkinMilk @southrivers 你们说的不对，可能对算法的执行过程还是不熟悉，不妨自己画个图手动执行一下算法逻辑就理解了。
以你们说的例子，节点 b 的 distFromStart 是 2，节点 f 的 distFromStart 是 3，这时候优先级队列会优先走 b，也就走到 c 了，得到最小路径 a -> b -> c。
@apache1011, 第三题确实感觉转换成计算最小的failure_rate再结合东哥的模板和思路会更加好理解.
import heapq
class Solution:
def _build_graph(self, n, edges, succ_probs):
graph = [[] for _ in range(n)]
for edge, succ_prob in zip(edges, succ_probs):
graph[edge[0]].append([edge[1], succ_prob])
graph[edge[1]].append([edge[0], succ_prob])
return graph
def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
# build the graph for N nodes - by using edges and succ_prob lists
graph = self._build_graph(n, edges, succProb)
# set max value as place holder to help to calc the smaller failure rates
path_probs = [float('inf')] * n
# init failure rate should be 0
path_probs[start] = 0
pq = [State(start, 0)]
while pq:
curr_node = heapq.heappop(pq)
curr_id = curr_node.id
curr_prob = curr_node.prob
if curr_id == end:
# return 1 - the smallest_failure_rate
return 1 - curr_prob
# the current failure rate has been the smaller one
if path_probs[curr_id] < curr_prob:
continue
for nei_id, nei_prob in graph[curr_id]:
# 1 - (1 - failure_rate) * success_rate = evolved_failure_rate
nxt_node_prob = 1 - (1-path_probs[curr_id]) * nei_prob
if path_probs[nei_id] > nxt_node_prob:
path_probs[nei_id] = nxt_node_prob
heapq.heappush(pq, State(nei_id, nxt_node_prob))
return 0
class State:
def __init__(self, id, prob):
self.id = id
self.prob = prob
def __lt__(self, other):
# track the failure rate - needs to return smaller one
# so that 1 - smallest_failure_rate = max_success_rate
return self.prob < other.prob
js 版 dijkstra 模板
function dijkstra(start, /* end */) {
// 图中节点的个数
const n = graph.length;
// 记录最短路径的权重，你可以理解为 dp table
// 定义：distTo[i] 的值就是节点 start 到达节点 i 的最短路径权重
// 求最小值，所以初始化为正无穷
const distTo = new Array(n).fill(Infinity);
// base case，start 到 start 的最短距离就是 0
distTo[start] = 0;
// 优先级队列，dist 较小的排在前面
const q = new PriorityQueue((a, b) => a[1] < b[1]);
// 从起点 start 开始进行 BFS
q.push([start, 0]);
while (!q.isEmpty()) {
const [v, dist] = q.pop();
// // 如果只要到 end, 在这里加一个判断就行了，其他代码不用改
// if (v === end) {
// return dist;
// }
if (dist > distTo[v]) {
// 已经有一条更短的路径到达 v 节点了
continue;
}
// 将相邻节点装入队列
for (const n of graph[v]) {
let distToN = distTo[v] + weight(v, n);
// 看看从 v 达到 n 的距离是否会更短
if (distToN < distTo[n]) {
// 更新 dp table
distTo[n] = distToN;
q.push([n, distToN]);
}
}
}
// // 如果只要到 end, 如果运行到这里，说明从 start 无法走到 end
// return Infinity
return distTo;
}
可以运行的 js 版 743. 网络延迟时间
var networkDelayTime = function(times, n, k) {
const graph = buildGraph();
const distTo = dijkstra(k);
// 找到最长的那一条最短路径
let result = 0;
for (let i = 1; i < distTo.length; i++) {
if (distTo[i] === Infinity) {
return -1;
}
result = Math.max(result, distTo[i]);
}
return result;
function buildGraph() {
// 节点编号是从 1 开始的，所以要一个大小为 n + 1 的邻接表
const graph = new Array(n + 1).fill(0).map(() => []);
// 构造图
for (const [from, to, weight] of times) {
// 邻接表存储图结构，同时存储权重信息
graph[from].push([to, weight]);
}
return graph;
}
function dijkstra(start) {
// 图中节点的个数
const n = graph.length;
// 记录最短路径的权重，你可以理解为 dp table
// 定义：distTo[i] 的值就是节点 start 到达节点 i 的最短路径权重
// 求最小值，所以初始化为正无穷
const distTo = new Array(n).fill(Infinity);
// base case，start 到 start 的最短距离就是 0
distTo[start] = 0;
// 优先级队列，dist 较小的排在前面
const q = new PriorityQueue((a, b) => a[1] < b[1]);
// 从起点 start 开始进行 BFS
q.push([start, 0]);
while (!q.isEmpty()) {
const [v, dist] = q.pop();
// // 在这里加一个判断就行了，其他代码不用改
// if (v === end) {
// return dist;
// }
if (dist > distTo[v]) {
// 已经有一条更短的路径到达 v 节点了
continue;
}
// 将相邻节点装入队列
for (const [n, weight] of graph[v]) {
let distToN = distTo[v] + weight;
// 看看从 v 达到 n 的距离是否会更短
if (distToN < distTo[n]) {
// 更新 dp table
distTo[n] = distToN;
q.push([n, distToN]);
}
}
}
// // 如果运行到这里，说明从 start 无法走到 end
// return Infinity
return distTo;
}
};
class PriorityQueue {
constructor(comparator = (a, b) => a > b) {
this._heap = [];
this._comparator = comparator;
}
size() {
return this._heap.length;
}
isEmpty() {
return this.size() === 0;
}
peek() {
return this._heap[0];
}
_parent(idx) {
return Math.floor((idx - 1) / 2);
}
_leftChild(index) {
return index * 2 + 1;
}
_rightChild(index) {
return index * 2 + 2;
}
_swap(i, j) {
[this._heap[i], this._heap[j]] = [this._heap[j], this._heap[i]];
}
_compare(i, j) {
return this._comparator(this._heap[i], this._heap[j]);
}
push(value) {
this._heap.push(value);
this._shifUp();
return this.size();
}
_shifUp() {
let idx = this.size() - 1;
while (idx > 0) {
const parent = this._parent(idx);
if (this._compare(idx, parent)) {
this._swap(idx, parent);
} else {
break;
}
idx = parent;
}
}
pop() {
let top = this.peek();
this._heap[0] = this._heap[this.size() - 1];
this._heap.length = this._heap.length - 1;
this._siftDown();
return top;
}
_siftDown() {
let idx = 0;
while (idx < this.size()) {
let leftIdx = this._leftChild(idx);
if (leftIdx >= this.size()) break;
let rightIdx = this._rightChild(idx);
let targetIdx = leftIdx;
if (rightIdx < this.size()) {
targetIdx = this._compare(leftIdx, rightIdx) ? leftIdx : rightIdx;
}
if (this._compare(targetIdx, idx)) {
this._swap(targetIdx, idx);
} else {
break;
}
idx = targetIdx;
}
}
}
if (curDistFromStart > distTo[curNodeID]) {
// 已经有一条更短的路径到达 curNode 节点了
continue;
}
- 网络延迟时间（中等） python version
import collections
import heapq
class State(object):
def __init__(self, id, dist_from_start):
self.id = id
self.dist_from_start = dist_from_start
def __lt__(self, other):
if self.dist_from_start < other.dist_from_start:
return True
return False
def dijkstra(graph, start):
n = len(graph)
dist_to = [float("inf")] * (n + 1)
# base case:start to start
dist_to[start] = 0
pq = []
heapq.heappush(pq, State(start, 0))
while pq:
cur_state = heapq.heappop(pq)
cur_node_id, cur_node_dist_from_start = cur_state.id, cur_state.dist_from_start
# 已经有一条更短的路径到达cur_node节点
if cur_node_dist_from_start > dist_to[cur_node_id]:
continue
for next_node in graph[cur_node_id]:
# 判断是否前进到下个节点
next_node_id, weight = next_node
dist_to_next_node = dist_to[cur_node_id] + weight
if dist_to_next_node < dist_to[next_node_id]:
dist_to[next_node_id] = dist_to_next_node
heapq.heappush(pq, State(next_node_id, dist_to_next_node))
return dist_to
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
# 构建图
graph = collections.defaultdict(list)
for i in range(1, n + 1):
graph[i] = []
for time in times:
_from, _to, weight = time
graph[_from].append((_to, weight))
dist_to = dijkstra(graph, k)
res = 0
for i in range(1, len(dist_to)):
if dist_to[i] == float("inf"):
return -1
res = max(res, dist_to[i])
return res
1631 题「 最小体力消耗路径」python version
import collections
import heapq
class State(object):
def __init__(self, x, y, effort_from_start):
self.x = x
self.y = y
self.effort_from_start = effort_from_start
def __lt__(self, other):
return self.effort_from_start < other.effort_from_start
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def adj(matrix, x, y):
# 返回坐标(x,y)的上下左右相邻坐标
m, n = len(matrix), len(matrix[0])
# 存储相邻节点
neighbors = []
for _dir in dirs:
nx = x + _dir[0]
ny = y + _dir[1]
if nx >= m or nx < 0 or ny >= n or ny < 0: # 索引越界
continue
neighbors.append((nx, ny))
return neighbors
class Solution:
def minimumEffortPath(self, heights: List[List[int]]) -> int:
m, n = len(heights), len(heights[0])
# 定义: 从(0,0)到(i,j)的最小体力消耗是effort_to[i][j]
effort_to = [[float("inf")] * n for _ in range(m)]
# base case 从自己到自己就是0
effort_to[0][0] = 0
pq = []
heapq.heappush(pq, State(0, 0, 0))
while pq:
cur_state = heapq.heappop(pq)
cur_x, cur_y, cur_effort_from_start = cur_state.x, cur_state.y, cur_state.effort_from_start
if cur_x == m - 1 and cur_y == n - 1:
return cur_effort_from_start
if cur_effort_from_start > effort_to[cur_x][cur_y]:
continue
for neighbor in adj(heights, cur_x, cur_y):
next_x, next_y = neighbor[0], neighbor[1]
# 计算从(cur_x,cur_y)达到(next_x,next_y)的消耗
effort_to_next_node = max(effort_to[cur_x][cur_y], abs(
heights[cur_x][cur_y] - heights[next_x][next_y]))
# 更新dp table
if effort_to[next_x][next_y] > effort_to_next_node:
effort_to[next_x][next_y] = effort_to_next_node
heapq.heappush(
pq, State(next_x, next_y, effort_to_next_node))
return -1
1514 题「 概率最大的路径」 python version
import heapq
import collections
class State(object):
def __init__(self, id, prob_from_start):
self.id = id
self.prob_from_start = prob_from_start
def __lt__(self, other): # 大顶堆
return self.prob_from_start > other.prob_from_start
class Solution:
def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
graph = collections.defaultdict(list)
for i in range(n):
graph[i] = []
# 构建图 无向图等价于双向图
for i in range(len(edges)):
_from,_to,weight = edges[i][0],edges[i][1],succProb[i]
graph[_from].append((_to, weight))
graph[_to].append((_from, weight))
prob_to = [-1] * n
# base case
prob_to[start] = 1
pq = []
heapq.heappush(pq, State(start, 1))
while pq:
cur_node = heapq.heappop(pq)
cur_node_id, cur_prob_from_start = cur_node.id, cur_node.prob_from_start
if cur_node_id == end:
return cur_prob_from_start
if cur_prob_from_start < prob_to[cur_node_id]:
# 如果当前节点的累积已经比之前的小，直接跳过（再乘只会越来越小）
continue
for neighbor in graph[cur_node_id]:
next_node, weight = neighbor
next_node_prob_from_start = prob_to[cur_node_id] * weight
if next_node_prob_from_start > prob_to[next_node]:
prob_to[next_node] = next_node_prob_from_start
heapq.heappush(
pq, State(next_node, next_node_prob_from_start))
return 0.0
关于@JackShang94和@XiaoyuZhou-hub的疑问，我认为出现这样的疑问的原因是：代码的枝剪部分规定只有当curDistFromStart <= distTo[curNodeID]时才会继续后面的for loop。这么看来curDistFromStart似乎有可能会小于distTo[curNodeID]，而for loop中计算distToNextNode时用的却是可能比curDistFromStart更大的distTo[curNodeID]（衍生而出的问题就是既然distTo[curNodeID]可能比curDistFromStart大，那么为什么不先更新distTo[curNodeID]的值？）。
...
if (curDistFromStart > distTo[curNodeID]) {
// 已经有一条更短的路径到达 curNode 节点了
continue;
}
// 将 curNode 的相邻节点装入队列
for (int nextNodeID : adj(curNodeID)) {
// 看看从 curNode 达到 nextNode 的距离是否会更短
int distToNextNode = distTo[curNodeID] + weight(curNodeID, nextNodeID);
...
那么问题实际上是什么时候会出现curDistFromStart > distTo[curNodeID]？什么时候会出现curDistFromStart < distTo[curNodeID]？
其实trace一遍distTo和pq中元素值的变化就可以明白，以文中的下图为例：
首先要说明下东哥的代码是在节点入队pq之前更新distTo数组，而不是在出队时更新。
当while loop循环完第3轮后distTo[5]的值为10，而pq内的元素为[[1, 9], [5, 10], [5, 11]]（格式是{nodeID, distFromStart}）。可以看到在[5, 10]入队的同时，distTo[5]的值也由11更新为10，同时pq中会同时存在[5, 10]和[5, 11]。
什么时候会存在curDistFromStart > distTo[curNodeID]？
当[5, 11]出队时，由于此时distTo[5]的值为10，便不再进入后续for loop。因为distTo[5]的值没有更新，那么就算进入后续的for loop，与5号节点相邻节点的distTo的值也不会更新。
什么时候会存在curDistFromStart < distTo[curNodeID]？为什么要用distTo[curNodeID]来计算distToNextNode？
事实上curDistFromStart并不会小于distTo[curNodeID]。前面提到过，distTo内的值都是在节点入队之前更新的，也就是说是先更新的distTo再将节点入队。而curDistFromStart是在节点出队时得到的，也就是说curDistFromStart只会大于distTo[curNodeID]（curDistFromStart入队之后distTo[curNodeID]被更小的值更新了）或者等于distTo[curNodeID]（curDistFromStart入队之后distTo[curNodeID]没被更新）。
使用distTo[curNodeID]来计算distToNextNode的原因我认为是在定义上distTo中存储的是节点到起点的最短距离。虽然由于枝剪代码的存在，当计算distToNextNode时，curDistFromStart只可能等于distTo[curNodeID]（如之前所述，本来就不存在小于的情况，枝剪代码又去掉了大于的情况），但是根据算法最初的定义，起点到邻居节点的最短距离=起点到当前节点的最短距离+当前节点到邻居节点的距离，所以distTo[curNodeID]才是计算时应该使用的变量。而distTo[curNodeID]不可能大于curDistFromStart由于是一个隐藏条件，结合枝剪代码，可能造成了一些误解。
@mingweiarthurli 给你点赞，写的很详细，这个算法的细节确实容易绕不清楚，我说下我的理解：
distTo[id] 永远维护到达 id 节点的最小距离，而 State 里面那个 distFromStart，维护的是 State.id 这个节点入队时距离起点的距离；该 State 会在队列中停留一段时间，等它被再次拿出队列的时候，distTo[State.id] 可能已经被更新成更小的值了。
比如这幅图，你手动执行一下算法：
节点 5 第一次入队时 State 记录的 distFromStart 是 11，但等这个 State 出队时，distTo[5] 已经更新成了 10，所以当然需要被这段逻辑 continue 掉：
if (curDistFromStart > distTo[curNodeID]) {
// 已经有一条更短的路径到达 curNode 节点了
continue;
}
有一个问题，用priorityqueue复杂度是O(ElogE)，那用linkedlist是不是就只有O(E)了？虽然linkedlist更慢但是worst case却更好？
