Patterns

Min-heap based shortest path on weighted graphs (non-negative weights)

When to useShortest path with edge weights; cheapest flights with K stops; network delay time

iterative

Dijkstra's Algorithm | Shortest Path in a Weighted Graph

dijkstra_intro

Maximal Minimum Value Path II

maximum_minimum_value_path_ii

Train Ride III

train_ride_3

INITIALIZE

dist[i] = Infinity (start = 0); min-heap with [0, start]

const dist = new Array(n).fill(Infinity);
dist[source] = 0;
const heap = new MinHeap();
heap.push([0, source]);

const visited = Array.from({ length: m }, () => new Array(n).fill(false));
const heap = new MaxHeap();
heap.push([grid[0][0], 0, 0, grid[0][0]]);

const dist = new Array(n + 1).fill(Infinity);
dist[1] = 0;
const heap = new MinHeap();
heap.push([0, 1]);

TRAVERSE

while heap not empty

while (heap.size() > 0) {

while (heap.size() > 0) {

while (heap.size() > 0) {

extract min

pop smallest [d, node]; skip if d > dist[node]

  const [d, node] = heap.pop();

—

  const [d, node] = heap.pop();

[RELAX]

for each neighbor: if d + weight < dist[next], update and push

  for (const [next, w] of graph[node]) {
    const nd = d + w;
    if (nd < dist[next]) {
      dist[next] = nd;
      heap.push([nd, next]);
    }
  }

  for (const [dr, dc] of dirs) {
    const nr = r + dr, nc = c + dc;
    if (nr < 0 || nr >= m || nc < 0 || nc >= n || visited[nr][nc]) continue;
    const newMin = Math.min(minSoFar, grid[nr][nc]);
    heap.push([newMin, nr, nc, newMin]);
  }

  for (const [next, time] of getEdges(node, maxLine, useTeleport)) {
    const nd = d + time;
    if (nd < dist[next]) {
      dist[next] = nd;
      heap.push([nd, next]);
    }
  }

RETURN

return dist[target] (or full dist array)

return dist;

return -1;

return dist[n] <= t;