Dijkstra 算法
这篇文章会讲解 Dijkstra 算法的概念和运作方式,以及 Programmers 的 [迷宫逃脱] 问题。
Dijkstra 算法是在图中寻找从一个顶点到其他所有顶点的最短路径的算法。
它可以用于计算机网络、导航等许多需要进行路径搜索的领域。
1. 基本概念
Dijkstra 算法基于以下几个核心概念。
加权图:每条边都带有非负权重的图
起点 :最短路径开始的节点
距离数组:各节点之间的最短距离
优先队列:在待访问的节点中,按累计成本从小到大排序的队列
设顶点数为 V、边数为 E,Dijkstra 算法的时间复杂度计算如下。
使用优先队列时,时间复杂度为 O(VlogV + ElogV)。
每次循环中,用优先队列更新未访问节点中从起点到当前为止的累计最短距离,需要 O(VlogV) 的时间。
为每个节点更新相邻节点的最短距离,需要 O(ElogV) 的时间。
如果存在负权重,就要使用 Bellman-Ford 算法。
2. 运作方式
Dijkstra 算法通常按照以下步骤进行。
初始化距离数组
把起始节点的距离设为 0,其余节点设为无穷大。

选择最近的节点
选择队列中与起点相邻的节点,并把它们加入队列。

更新距离
检查所选节点的相邻节点,一旦发现从起点出发尚未访问过的路径,就持续更新距离数组。





当所有节点都被访问过,或者没有可以再更新的路径时,算法结束。

在这个过程中,为了先探索累计距离更短的路径,会使用优先队列(Priority Queue),因此先访问到的节点的累计距离值就是最短距离值。
3. 优先队列
Dijkstra 算法即使不用优先队列,也可以通过不断执行 sort 函数来实现。但这样时间复杂度不好,所以应该使用优先队列。因此,需要能够在 JavaScript 中实现高效的优先队列。下面给大家看一下优先队列的示例代码。
class PriorityQueue { constructor(comparator = (a, b) => a > b) { this.heap = []; this.comparator = comparator; // boolean comparator } size() { return this.heap.length; } isEmpty() { return this.size() === 0; } peek() { return this.heap[0]; } push(value) { this.heap.push(value); this._heapifyUp(); } pop() { if (this.isEmpty()) return null; const top = this.peek(); const last = this.heap.pop(); if (!this.isEmpty()) { this.heap[0] = last; this._heapifyDown(); } return top; } _heapifyUp() { let index = this.size() - 1; const element = this.heap[index]; while (index > 0) { const parentIndex = Math.floor((index - 1) / 2); const parent = this.heap[parentIndex]; if (!this.comparator(element, parent)) break; this.heap[index] = parent; index = parentIndex; } this.heap[index] = element; } _heapifyDown() { let index = 0; const length = this.size(); const element = this.heap[0]; while (true) { const leftIndex = 2 * index + 1; const rightIndex = 2 * index + 2; let swapIndex = null; if (leftIndex < length && this.comparator(this.heap[leftIndex], element)) { swapIndex = leftIndex; } if ( rightIndex < length && ((swapIndex === null && this.comparator(this.heap[rightIndex], element)) || (swapIndex !== null && this.comparator(this.heap[rightIndex], this.heap[leftIndex]))) ) { swapIndex = rightIndex; } if (swapIndex === null) break; this.heap[index] = this.heap[swapIndex]; index = swapIndex; } this.heap[index] = element; }}4. 实战例题 - [Programmers] 迷宫逃脱

下面给大家看看我在迷宫逃脱问题中是如何利用 Dijkstra 算法解题的代码。题目说明比较长,我另外附上链接。
题目说明:需要求出从出发地到目的地的最短距离值。节点分为普通节点和陷阱节点。
题目要点:
需要用 Dijkstra 算法求出从出发地 X 到目的地 Y 的距离。
边是有方向的。
A 节点和 B 节点之间可能存在多条边。
节点中存在陷阱节点,到达陷阱节点时,与该陷阱节点相连的所有边的方向都会反转。
出发地和目的地都不是陷阱节点。
从出发地总是可以到达目的地。
解题要点:
不是求从出发地 X 到所有节点的距离,而是只要求出与特定 X 节点之间的距离就应该结束。
A 节点和 B 节点之间的边,每个方向只保留权重最小的那条。
不需要考虑没有目的地的情况。(不需要处理找不到的异常。)
因为有陷阱,所以会出现同一个节点被踩 2 次的情况。
为了知道哪些节点的边会发生变化,除了节点、边的信息之外,似乎还需要额外保存状态值。
下面是我第一次作为正确答案提交的代码。因为做得很急,从变量名开始全都乱七八糟。上面的 [3. 优先队列] 和下面代码中的优先队列的不同之处在于,这里是用 literal object 实现的。两种方法的速度差不多,但据说在 V8 引擎优化中,literal object 可能更不利。(我个人推测,可能是因为按照 V8 引擎的优化方式,它不是同一类型的重复,所以不会发生类型模板缓存。也可能是错的,大家可以自己学习一下。)
class PriorityQueue { constructor(oper) { this.items = {}; this.tail = 0; this.oper = oper; } push(item) { const pushIndex = this.tail++; this.items[pushIndex] = item; this.heapUp(pushIndex); } pop() { if (this.isEmpty()) return undefined; const item = this.items[0]; const lastIndex = --this.tail; [this.items[0], this.items[lastIndex]] = [this.items[lastIndex], this.items[0]]; delete this.items[lastIndex]; if (!this.isEmpty()) this.heapDown(0); return item; } isEmpty() { return 0 === this.tail; } size() { return this.tail; } getParentIndex(index) { const parentIndex = Math.floor((index-1)/2); if(parentIndex < 0) return null; return parentIndex; } swapParent(index) { const parentIndex = Math.floor((index-1)/2); if(parentIndex < 0) return null; [this.items[index], this.items[parentIndex]] = [this.items[parentIndex],this.items[index]] } heapUp(index) { const item = this.items[index]; const parentIndex = this.getParentIndex(index) if(parentIndex === null) return; const parent = this.items[parentIndex]; if(this.oper(item, parent)){ this.swapParent(index); this.heapUp(parentIndex); } } heapDown(index) { const item = this.items[index]; const lIndex = index*2+1; const rIndex = index*2+2; if(this.tail <= lIndex) return; if(this.tail <= rIndex) { if(this.oper(this.items[lIndex],item)) [this.items[lIndex], this.items[index]] = [this.items[index], this.items[lIndex]] return this.heapDown(lIndex); } if(this.oper(this.items[lIndex],this.items[rIndex])) { if(this.oper(this.items[lIndex],item)) { [this.items[lIndex], this.items[index]] = [this.items[index], this.items[lIndex]] return this.heapDown(lIndex); } } else { if(this.oper(this.items[rIndex],item)) { [this.items[rIndex], this.items[index]] = [this.items[index], this.items[rIndex]] return this.heapDown(rIndex); } } }}// [当前位置, 移动距离]function solution(n, start, end, roads, traps) { const MAP = Array.from(Array(n+1),()=>Array(n+1).fill(0)) const visited = Array.from(Array(n+1),()=>[Math.infinite, Math.infinite]) roads.forEach((road)=>{ if(MAP[road[0]][road[1]] === 0) MAP[road[0]][road[1]]=road[2] else if(MAP[road[0]][road[1]] > road[2]) MAP[road[0]][road[1]] = road[2]; }) const queue = new PriorityQueue((item1,item2) => (item1[1] < item2[1])); queue.push([start,0,0,{},{}]) const trapsDict = traps.reduce((prev, trap)=>({...prev,[trap]:true}), {}) const answer = dik(queue, start, end, MAP, visited, trapsDict); return answer;}function dik(queue, start, end, Map, visited,traps) { const current = queue.pop(); // [位置, 移动距离, 次数, trapped] const [pos,dis,count,trapped,visited2] = current; const isTrap = traps[pos]; if(pos === end) return dis; if(count >= 2) return dik(queue, start, end, Map, visited, traps); if(dis > visited[pos][count]) return dik(queue, start, end, Map, visited, traps); visited[pos][count] = dis; const visitedCopy = {...visited2} if(visitedCopy[pos]) { visitedCopy[pos] += 1; } else { visitedCopy[pos] = 1; } const newTrapped = {...trapped}; if(isTrap){ newTrapped[pos] = newTrapped[pos]? 2: 1 } const newMap2 = [...Map[pos]]; if(isTrap && newTrapped[pos]!==2) { for(let i=1; i<newMap2.length; i++) { newMap2[i] = Map[i][pos]; } } Object.keys(trapped).forEach((trap)=> { if(newMap2[trap] === Map[trap][pos]) newMap2[trap] = Map[pos][trap]; else newMap2[trap] = Map[trap][pos]; }) newMap2.forEach((to,index)=> { if(to) { const visitTrapCount = newTrapped[index] ?? 0; const visitCount = visitedCopy[index] ?? 0; if(visitTrapCount>1) return; if(visitCount >1) return; queue.push([index,to+dis,visitCount,newTrapped,visitedCopy]) } }) return dik(queue, start, end, Map, visited, traps);}下面我把上面的代码连同变量名一起改得更整洁一些。
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]; } push(value) { this.heap.push(value); this._heapifyUp(); } pop() { if (this.isEmpty()) return null; const top = this.peek(); const last = this.heap.pop(); if (!this.isEmpty()) { this.heap[0] = last; this._heapifyDown(); } return top; } _heapifyUp() { let index = this.size() - 1; const element = this.heap[index]; while (index > 0) { const parentIndex = Math.floor((index - 1) / 2); const parent = this.heap[parentIndex]; if (!this.comparator(element, parent)) break; this.heap[index] = parent; index = parentIndex; } this.heap[index] = element; } _heapifyDown() { let index = 0; const length = this.size(); const element = this.heap[0]; while (true) { const leftIndex = 2 * index + 1; const rightIndex = 2 * index + 2; let swapIndex = null; if (leftIndex < length && this.comparator(this.heap[leftIndex], element)) { swapIndex = leftIndex; } if ( rightIndex < length && ((swapIndex === null && this.comparator(this.heap[rightIndex], element)) || (swapIndex !== null && this.comparator(this.heap[rightIndex], this.heap[leftIndex]))) ) { swapIndex = rightIndex; } if (swapIndex === null) break; this.heap[index] = this.heap[swapIndex]; index = swapIndex; } this.heap[index] = element; }}// [当前位置, 累计距离, 访问次数, 已激活的陷阱状态, 访问记录]function solution(n, start, end, roads, traps) { const graph = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0)); // [第一次踩到节点时的最短距离, 第二次踩到节点时的最短距离] const distanceRecord = Array.from({ length: n + 1 }, () => [Infinity, Infinity]); // 初始化图 roads.forEach(([from, to, cost]) => { if (graph[from][to] === 0 || graph[from][to] > cost) { graph[from][to] = cost; } }); const pq = new PriorityQueue((a, b) => a[1] < b[1]); pq.push([start, 0, 0, {}, {}]); const trapSet = traps.reduce((acc, trap) => ({ ...acc, [trap]: true }), {}); return dijkstra(pq, end, graph, distanceRecord, trapSet);}function dijkstra(pq, end, graph, distanceRecord, trapSet) { while (!pq.isEmpty()) { const current = pq.pop(); const [pos, totalDist, visitCount, activeTraps, visitHistory] = current; const isTrap = trapSet[pos]; if (pos === end) return totalDist; if (visitCount >= 2) continue; if (totalDist > distanceRecord[pos][visitCount]) continue; distanceRecord[pos][visitCount] = totalDist; // 更新访问记录 const newVisitHistory = { ...visitHistory }; newVisitHistory[pos] = (newVisitHistory[pos] ?? 0) + 1; // 更新陷阱激活状态 const newActiveTraps = { ...activeTraps }; if (isTrap) { newActiveTraps[pos] = newActiveTraps[pos] ? 2 : 1; } // 以当前位置为准可移动的边 const nextEdges = [...graph[pos]]; if (isTrap && newActiveTraps[pos] !== 2) { for (let i = 1; i < nextEdges.length; i++) { nextEdges[i] = graph[i][pos]; } } // 反映其他陷阱的影响 Object.keys(activeTraps).forEach((trap) => { if (nextEdges[trap] === graph[trap][pos]) { nextEdges[trap] = graph[pos][trap]; } else { nextEdges[trap] = graph[trap][pos]; } }); // 移动 nextEdges.forEach((cost, nextPos) => { if (cost) { const trapVisitCount = newActiveTraps[nextPos] ?? 0; const nodeVisitCount = newVisitHistory[nextPos] ?? 0; if (trapVisitCount > 1) return; if (nodeVisitCount > 1) return; pq.push([nextPos, totalDist + cost, nodeVisitCount, newActiveTraps, newVisitHistory]); } }); } return -1; // 无法到达}我来补充一下解说:上面的代码为什么这样改、为什么没改。
上面的代码中,有没有和 Dijkstra 算法说明不一样的实现部分呢??
有的。我觉得如果节点已经访问过,一开始就不把它放进优先队列会更快。但我因为一直在考虑由于陷阱而访问 2 次的情况,好像没来得及想到这一点。大家在实现时,如果 distanceRecord[nodeVisitCount][nextPos] 已经被访问过,就干脆不要放进 queue!! 我觉得那样会更快。
为什么要另外一起传递 activeTraps?
虽然只凭 newVisitHistory 和 traps 信息也能知道哪些陷阱被触发了,但我觉得查找已触发的陷阱可能会花很多时间,所以另外用 Map 数据类型来保存 activeTraps。
用 N X M 数组保存图的边信息,会不会占用太多内存?
是的,节点数量一多,就会占用大量内存。所以如果用 Map 数据类型让每个节点保存自己的边,就能节省很多内存。但这样就需要确认节点之间是否存在边,所以会比通过数组的 index 访问更慢。在这个 trade off 关系中,我更看重速度。
你把 Dijkstra 算法的处理改成了执行到 heap 为空为止的 while 循环,为什么要改?
function 递归函数在每次被调用时,都会在 Stack 区域中堆积函数。也就是说,while 循环只需要新建 Scope 就行,而用递归函数处理时,每执行一次函数就要创建执行上下文,相应地会产生更多开销。
能不能处理得更快呢?
这个嘛?? 嗯,暂时想不到什么。要做位运算的话,数组好像都太长了... 要用 ArrayBuffer 的话,因为用的是大小可变的数据类型,好像也不行。硬要找的话,用 Worker 会不会可以呢..? 我也不太清楚。

