Dijkstra's algorithm finds the shortest distance from a Single Source to all other nodes in a weighted graph (where weights are positive).

Think of a Fire Spreading through a Network of Pipes:

1. You light a fire at Node $A$.
2. The fire travels through the pipes at a speed determined by the pipe's length (Weight).
3. The first time the fire reaches a node, that is the Shortest Possible Time to get to that node!
4. You always prioritize the "puddle" of fire that is currently at the smallest time (Greedy).

---

The Greedy Choice

Dijkstra always picks the unvisited node with the smallest known distance. To do this efficiently, we use a Min-Priority Queue.

Complexity Analysis

• Time: $O((V + E) \log V)$ using a Binary Heap.
• Space: $O(V + E)$ to store the graph and the distance array.

Limitation

Dijkstra cannot handle negative weights. If there are negative edges, use the Bellman-Ford Algorithm.

---

javascript Standard
/**
 * Shortest Path using Dijkstra - O((V+E) log V)
 */
function dijkstra(n, adj, startNode) {
  const dist = new Array(n).fill(Infinity);
  const pq = new MinPriorityQueue(); // Format: [dist, node]

  dist[startNode] = 0;
  pq.push([0, startNode]);

  while (!pq.isEmpty()) {
    const [d, u] = pq.pop();

    // If we've already found a better path, skip
    if (d > dist[u]) continue;

    for (const [v, weight] of adj.get(u)) {
      if (dist[u] + weight < dist[v]) {
        dist[v] = dist[u] + weight;
        pq.push([dist[v], v]);
      }
    }
  }

  return dist;
}

---

Variations

• Print the Path: Store a parent array. parent[v] = u whenever you update a distance.
• Single Source Single Target: Stop the algorithm as soon as you "pop" the target node from the Priority Queue.
• A Search*: An optimized version of Dijkstra that uses a heuristic to "guide" the search towards the target.

Common Questions

• Why doesn't Dijkstra work with negative edge weights?
• What is the difference between Dijkstra and Prim's algorithm? (Answer: Dijkstra builds a path to a source; Prim's builds a Minimum Spanning Tree).
• Implement Dijkstra using an Adjacency Matrix ($O(V^2)$). 🚁