Dijkstra Shortest Path With Priority Queue

export type WeightedGraph = ReadonlyMap<string, ReadonlyArray<readonly [string, number]>>;

interface HeapEntry {
  readonly node: string;
  readonly distance: number;
}

export interface ShortestPaths {
  readonly distances: ReadonlyMap<string, number>;
  pathTo(target: string): string[];
}

export function shortestPaths(graph: WeightedGraph, source: string): ShortestPaths {
  if (!(graph instanceof Map)) throw new TypeError("graph must be a Map");
  if (!graph.has(source)) throw new RangeError(`unknown source "${source}"`);

  const distances = new Map<string, number>([[source, 0]]);
  const previous = new Map<string, string>();
  const heap: HeapEntry[] = [{ node: source, distance: 0 }];
  const settled = new Set<string>();

  while (heap.length > 0) {
    const current = pop(heap);
    if (current === undefined) break;
    if (settled.has(current.node)) continue;
    settled.add(current.node);

    const edges = graph.get(current.node);
    if (edges === undefined) continue;
    for (const [neighbor, weight] of edges) {
      if (!Number.isFinite(weight) || weight < 0) {
        throw new RangeError(`edge "${current.node}" -> "${neighbor}" has an invalid weight`);
      }
      const candidate = current.distance + weight;
      const known = distances.get(neighbor);
      if (known === undefined || candidate < known) {
        distances.set(neighbor, candidate);
        previous.set(neighbor, current.node);
        push(heap, { node: neighbor, distance: candidate });
      }
    }
  }

  return {
    distances,
    pathTo(target: string): string[] {
      if (!distances.has(target)) return [];
      const path: string[] = [];
      let cursor: string | undefined = target;
      while (cursor !== undefined) {
        path.push(cursor);
        cursor = previous.get(cursor);
      }
      return path.reverse();
    },
  };
}

function push(heap: HeapEntry[], entry: HeapEntry): void {
  let index = heap.length;
  heap.push(entry);
  while (index > 0) {
    const parent = (index - 1) >> 1;
    const parentEntry = heap[parent];
    if (parentEntry === undefined || parentEntry.distance <= entry.distance) break;
    heap[index] = parentEntry;
    index = parent;
  }
  heap[index] = entry;
}

function pop(heap: HeapEntry[]): HeapEntry | undefined {
  const first = heap[0];
  const last = heap.pop();
  if (first === undefined || last === undefined || heap.length === 0) return first;
  let index = 0;
  while (true) {
    const left = index * 2 + 1;
    const right = left + 1;
    let smallest = index;
    let smallestEntry = last;
    const leftEntry = heap[left];
    if (leftEntry !== undefined && leftEntry.distance < smallestEntry.distance) {
      smallest = left;
      smallestEntry = leftEntry;
    }
    const rightEntry = heap[right];
    if (rightEntry !== undefined && rightEntry.distance < smallestEntry.distance) {
      smallest = right;
      smallestEntry = rightEntry;
    }
    if (smallest === index) break;
    heap[index] = smallestEntry;
    index = smallest;
  }
  heap[index] = last;
  return first;
}

const graph: WeightedGraph = new Map([
  ["a", [["b", 2], ["c", 5]]],
  ["b", [["c", 1], ["d", 7]]],
  ["c", [["d", 2]]],
  ["d", []],
]);
const result = shortestPaths(graph, "a");
console.log([...result.distances.entries()]);
console.log(result.pathTo("d"));
console.log(result.pathTo("missing"));