Contents (5)
Dijkstra's Algorithm
In this post, I'll explain the concept of Dijkstra's algorithm, how it works, and the [Maze Escape] problem from Programmers.
Dijkstra's algorithm is an algorithm that finds the shortest paths from one vertex of a graph to all the other vertices.
It can be used in many fields that need pathfinding, like computer networks and navigation.
1. Basic Concepts
Dijkstra's algorithm is based on the following key concepts.
Weighted graph: a graph where every edge has a non-negative weight
Starting point: the node where the shortest path begins
Distance array: the shortest distance between each node
Priority queue: a queue that sorts the nodes to visit in order of lowest accumulated cost
If V is the number of vertices and E is the number of edges, the time complexity of Dijkstra's algorithm is calculated like this.
When you use a priority queue, the time complexity is O(VlogV + ElogV).
In each loop iteration, it takes O(VlogV) time to update, with the priority queue, the accumulated shortest distance from the starting point so far among the unvisited nodes.
For each node, it takes O(ElogV) time to update the shortest distances of its neighboring nodes.
If there are negative weights, you need to use the Bellman-Ford algorithm instead.
2. How It Works
Dijkstra's algorithm usually follows these steps.
Initialize the distance array
Set the distance of the starting node to 0 and the rest of the nodes to infinity.

Select the closest node
Select the nodes adjacent to the starting point in the queue and add them to the queue.

Update the distances
While checking the neighbors of the selected node, keep updating the distance array whenever an unvisited path from the starting point is found.





The algorithm ends when every node has been visited or there are no more paths to update.

In this process, a Priority Queue is used so that paths with shorter accumulated distances are explored first, which means the accumulated distance of a node when it's first visited is its shortest distance.
3. Priority Queue
You can implement Dijkstra's algorithm without a priority queue by repeatedly running a sort function. But the time complexity isn't great, so you should use a priority queue. That's why you need to be able to implement an efficient priority queue in JavaScript. Let me show you some example priority queue code.
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. Practice Problem - [Programmers] Maze Escape

I'll show you the code for how I used Dijkstra's algorithm to solve the Maze Escape problem. The problem description is long, so I'll attach a separate link.
Problem description: You need to find the shortest distance from the start to the destination. There are regular nodes and trap nodes.
Key points of the problem:
You need to use Dijkstra's algorithm to find the distance from the start X to the destination Y.
The edges have directions.
There can be multiple edges between node A and node B.
Some nodes are traps, and when you arrive at a trap node, the direction of every edge connected to that trap node is reversed.
The start and destination aren't trap nodes.
You can always get from the start to the destination.
Key points of the solution:
Instead of finding the distances from the start X to every node, you should stop as soon as you've found the distance to the specific node X.
Between node A and node B, you should keep only the minimum-weight edge in each direction.
You don't need to think about the case where there's no destination. (No exception handling for not finding it is needed.)
Because there are traps, you can end up stepping on the same node twice.
To know which nodes have their edges flipped, it looks like you need to store an extra state value on top of the node and edge information.
Below is the code I first submitted as my answer. I was rushing to solve it, so everything is a mess, starting with the variable names. The difference between the priority queue in [3. Priority Queue] above and the one in the code below is that this one is implemented with a literal object. Both approaches came out at about the same speed, but apparently a literal object can be worse for V8 engine optimization. (My personal guess is that, because of the way the V8 engine optimizes, type template caching probably won't happen since it isn't a repetition of the same type. I could be wrong, so try studying it yourself.)
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); } } }}// [current position, distance traveled]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(); // [position, distance traveled, count, 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);}Let me clean up the code above, including the variable names.
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; }}// [current position, accumulated distance, visit count, active trap state, visit history]function solution(n, start, end, roads, traps) { const graph = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0)); // [shortest distance on the 1st visit to the node, shortest distance on the 2nd visit to the node] const distanceRecord = Array.from({ length: n + 1 }, () => [Infinity, Infinity]); // Initialize the graph 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; // Update the visit history const newVisitHistory = { ...visitHistory }; newVisitHistory[pos] = (newVisitHistory[pos] ?? 0) + 1; // Update the trap activation state const newActiveTraps = { ...activeTraps }; if (isTrap) { newActiveTraps[pos] = newActiveTraps[pos] ? 2 : 1; } // Edges you can move along from the current position const nextEdges = [...graph[pos]]; if (isTrap && newActiveTraps[pos] !== 2) { for (let i = 1; i < nextEdges.length; i++) { nextEdges[i] = graph[i][pos]; } } // Apply the effects of other traps Object.keys(activeTraps).forEach((trap) => { if (nextEdges[trap] === graph[trap][pos]) { nextEdges[trap] = graph[pos][trap]; } else { nextEdges[trap] = graph[trap][pos]; } }); // Move 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; // Unreachable}Let me add some commentary on why I changed things in the code above, and why I didn't.
Is there any part of the code above that I implemented differently from the Dijkstra's algorithm explanation??
Yes. I think it would be faster not to put a node into the priority queue in the first place if it's already been visited. But I was so busy thinking about the case of visiting twice because of the traps that I guess I didn't get around to that. You should implement it so that if distanceRecord[nodeVisitCount][nextPos] has already been visited, it doesn't go into the queue at all!! I think that'll be faster.
Why do you pass activeTraps along separately?
You could figure out the triggered traps with just newVisitHistory and the traps information, but I thought finding the triggered traps might take a lot of time, so I kept activeTraps separately as a Map data structure.
Doesn't keeping the graph's edge information in an N X M array take up too much memory?
Yes, it takes up a lot of memory as the number of nodes grows. So if you use a Map data structure to hold the edges for each node, you can save a lot of memory. But then you'd have to check whether an edge exists for a node, so it would be slower than accessing it by array index. Since it's a trade off, I put more emphasis on speed.
You changed the Dijkstra's algorithm processing into a while loop that runs until the heap is empty. Why did you change it?
With a recursive function, a function gets stacked onto the Stack area every time it's called. In other words, a while loop only needs a new Scope, but if you handle it with a recursive function, an execution context has to be created every time the function runs, and that costs that much more.
Could it be made even faster?
Hmm, I'm not sure?? Well, nothing comes to mind right away. It seems like the arrays are all too long for bit operations... and ArrayBuffer won't work either, since I'm using data structures whose sizes vary. If I really had to find something, maybe using a Worker would work..? I'm not really sure.

