Designing Cloud-Native Systems & AI Workflows

export function dijkstra(graph: Graph, start: string, target: string) {
  const distances = new Map<string, number>();
  const previous = new Map<string, string>();
  const pq = new MinHeapPriorityQueue<string>();

  distances.set(start, 0);
  pq.insert(start, 0);

  while (!pq.isEmpty()) {
    const current = pq.extractMin();
    if (current === target) break;

    const currentDist = distances.get(current) ?? Infinity;

    for (const edge of graph.getNeighbors(current)) {
      const newDist = currentDist + edge.weight;
      if (newDist < (distances.get(edge.to) ?? Infinity)) {
        distances.set(edge.to, newDist);
        previous.set(edge.to, current);
        pq.insert(edge.to, newDist);
      }
    }
  }

  return reconstructPath(previous, target, distances.get(target));
}