Dijkstra's algorithm

Prerequisites

• BFS, the unweighted version of the idea.
• Priority queue.
• Weighted graphs (see representations).

The analogy

How it works

Precondition: all edge weights must be non-negative. With a negative edge, a settled distance could later improve, and Dijkstra would give wrong answers; use Bellman-Ford instead.

Start with one run by hand

Undirected edges: A–B 4, A–C 1, C–B 2, B–D 1, C–D 5. Start at A: dist A = 0, others ∞. Each round, settle the closest unsettled vertex and relax its edges. Predict, then open "Check".

Finish the picture: why negative weights break it

Directed edges: S → A 2, S → B 3, B → A −2.

• Dijkstra's answer. Predict what it settles first and the distance it reports for A.
  Check

  It settles A first at distance 2 (2 < 3) and never revisits it, reporting 2.

• The truth. Predict the real shortest distance to A.
  Check

  S → B → A costs 3 − 2 = 1. Dijkstra was wrong because the negative edge appeared after A was settled.

The rule in plain words

Set dist[start] = 0, all others ∞. Repeat: pick the unsettled vertex u with the smallest dist, settle it, and relax every edge u → v.

A min-priority queue makes "pick the smallest" fast; a plain array scan is simpler and fine for dense graphs.

The code

Read this code after you have done the run by hand. It will make more sense.

void dijkstra(int w[][4], int n, int s, int dist[]) {   /* w = 0 means no edge */
    int done[4] = {0};
    for (int i = 0; i < n; i++) dist[i] = INT_MAX;
    dist[s] = 0;
    for (int round = 0; round < n; round++) {
        int u = -1;
        for (int i = 0; i < n; i++)                         /* closest unsettled vertex */
            if (!done[i] && (u == -1 || dist[i] < dist[u])) u = i;
        if (dist[u] == INT_MAX) break;                     /* the rest is unreachable */
        done[u] = 1;
        for (int v = 0; v < n; v++)                         /* relax u's edges */
            if (w[u][v] && dist[u] + w[u][v] < dist[v]) dist[v] = dist[u] + w[u][v];
    }
}

graph LR
  A((A)) ---|4| B((B))
  A ---|1| C((C))
  C ---|2| B
  B ---|1| D((D))
  C ---|5| D
          

How fast is it?

Each vertex is settled once and each edge relaxed once. With a binary heap, every settle and every improvement costs $O(\log V)$:

The array version, used in the code above, is better for dense graphs where $E \approx V^2$.

Common mistakes

• Using it on a graph with a negative edge.
• Settling a vertex when it is first discovered instead of when it is the smallest remaining.
• Adding to ∞ in C (INT_MAX + w overflows): skip edges from unreachable vertices.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• The closest unsettled distance is final because non-negative edges can only make other routes longer.
• Negative edges break it because a settled distance could still be improved later.
• The heap version is $O((V + E) \log V)$ because each settle and each improvement is a heap operation.
• The array version is $O(V^2)$ because each of $V$ rounds scans all vertices.
• Relaxation is the core step because it's the only place distances get better.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is Dijkstra's algorithm like water spreading through pipes?
   Sample answer

   The water reaches the closest junction first and spreads from there; Dijkstra always settles the vertex the wave would reach next.

2. Walk through Dijkstra from A on A–B 4, A–C 1, C–B 2, B–D 1, C–D 5.
   Sample answer

   Settle A (B = 4, C = 1); settle C (B = 3, D = 6); settle B (D = 4); settle D. Final 0, 3, 1, 4.

3. Why does the code break when the closest distance is INT_MAX?

   A good answer says what those vertices are.

   Sample answer

   The remaining vertices can't be reached from the start, so there is nothing left to settle, and adding a weight to INT_MAX would overflow.

4. So what is Dijkstra's algorithm, in one sentence?
   Sample answer

   A single-source shortest-path algorithm for non-negative weights that repeatedly settles the closest unsettled vertex and relaxes its edges.

5. Why does Dijkstra require non-negative weights?

   A good answer uses the S → A, S → B, B → A example.

   Sample answer

   It settles A at 2 for good, but the path through B with the −2 edge costs 1. A negative edge can improve a distance after it was declared final.

6. What are the costs of the array and heap versions?
   Sample answer

   Array: $O(V^2)$. Binary heap: $O((V + E) \log V)$. Both use $O(V)$ extra space.

7. When would you choose BFS or Bellman-Ford instead?
   Sample answer

   BFS when all edges have the same weight; Bellman-Ford when some weights are negative.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the heap analysis and the overflow detail. I'd keep the water analogy, the 4-vertex run, and "settle the closest, relax its edges, no negative weights".

External resources

• VisuAlgo: Single-source shortest paths: run Dijkstra (and Bellman-Ford) on your own graph.
• GeeksforGeeks: Dijkstra's algorithm: array and heap versions with code.
• Wikipedia: Dijkstra's algorithm: history, proof and variants.
• MIT OCW 6.006: lecture on Dijkstra.

Videos

• YouTube search: Dijkstra explained: pick a walkthrough with a distance table.