Dijkstra's Algorithm

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source node to all other nodes in a weighted graph (with non-negative edge weights).

Weighted Graph

const graph = {
  "A": [["B", 4], ["C", 2]],
  "B": [["D", 3], ["C", 1]],
  "C": [["B", 1], ["D", 5]],
  "D": [],
};
// A→C (cost 2) → B (cost 1) → D (cost 3): total A→D = 6

Algorithm

1. Initialize distances: dist[start] = 0, all others = Infinity.
2. Maintain a set of unvisited nodes.
3. Repeatedly pick the unvisited node with the smallest tentative distance.
4. For each neighbor, if dist[node] + weight < dist[neighbor], update dist[neighbor].
5. Mark the node as visited.
6. Stop when all nodes are visited or the smallest tentative distance is Infinity.

function dijkstra(graph, start) {
  const dist = {};
  const visited = new Set();
  for (const node in graph) dist[node] = Infinity;
  dist[start] = 0;

  while (true) {
    // Pick unvisited node with smallest distance
    let node = null;
    for (const n in dist) {
      if (!visited.has(n) && (node === null || dist[n] < dist[node])) node = n;
    }
    if (node === null || dist[node] === Infinity) break;
    visited.add(node);

    for (const [neighbor, weight] of (graph[node] || [])) {
      if (dist[node] + weight < dist[neighbor]) {
        dist[neighbor] = dist[node] + weight;
      }
    }
  }
  return dist;
}

Complexity

This naive implementation is O(V²). With a priority queue (min-heap), it becomes O((V + E) log V), which is how real implementations work (e.g., Dijkstra in Google Maps).

Your Task

Implement dijkstra(graph, start) that returns an object mapping each node to its shortest distance from start.