Dijkstra's Algorithm: How Your Map Finds the Fastest Route

You type a destination into your maps app and hit Go. Between you and that address there are thousands of intersections and an absurd number of possible routes — more than you could list in a lifetime. The app answers in milliseconds, and it isn't guessing.

The engine behind that answer is Dijkstra's algorithm, and here's the good news: underneath the famous name sits one idea so natural that you already use it without noticing. Let's find it together, trace it on a real graph step by step, and then build it.

Let's start nowhere near a computer

Forget roads and apps for a minute. Imagine the streets of your neighbourhood are shallow canals, and at exactly noon you pour water into the canal at your front gate.

The water spreads down every canal at the same speed. It reaches the nearest junction first, then the next nearest, then the next — it physically cannot reach a junction 7 minutes away before one that's 5 minutes away.

   pour water here
        │
        ▼
       (You) ── 5 min ── (Market) ── 4 min ── (School)
         │                  │
       8 min              2 min
         │                  │
       (Park) ─── 1 min ─ (Temple)
 
   the flood arrives in order of distance, nearest first:
   You (0) → Market (5) → Temple (7) → Park (8) → School (9)

Look at the Park for a second. The direct canal from your gate is 8 minutes — but the water flowing You → Market → Temple → Park would take 5 + 2 + 1 = 8 minutes too, a dead heat. The flood doesn't care which canals the water used. The moment water first touches a junction is, by definition, the shortest time to reach it. No route can beat the flood, because every route is water.

Dijkstra's algorithm is nothing more than this flood, done with a notebook instead of water. We simulate which junction gets wet next, and that's the entire algorithm.

Where this flood runs in real life

• Your maps app. Roads are edges, travel times are weights. (Production systems add tricks on top — more on that at the end — but this is the foundation.)
• The internet itself. Routing protocols like OSPF run shortest-path computations so your packets take the cheapest path through the network.
• Games. When an enemy NPC navigates around walls to reach you, a shortest-path search is steering it.
• Ride-hailing and delivery apps. Matching you with the nearest driver and quoting an ETA is shortest-path arithmetic on a live road graph.

The graph we'll conquer

Here's the graph we'll use for the whole article — five places, six one-way roads, each with a cost:

    A ────4──── B
    │         ╱ │
    1       2   5
    │     ╱     │
    C ──╱       D ──3── E
     ╲          │
      ╲────8────┘
 
    roads: A→B (4)   A→C (1)   C→B (2)
           B→D (5)   C→D (8)   D→E (3)

Glance at A → B. The direct road costs 4, but sneaking around through C costs 1 + 2 = 3. Cheaper! Spotting that automatically — for every node, in any graph — is exactly the job.

The one rule that runs everything

Keep a notebook with the best-known cost to every place, starting with 0 for the start and ∞ (no idea yet) for everyone else. Then repeat one rule until done:

Among the places you haven't finalized yet, take the one with the smallest known cost — and declare it done. Forever.

That's the flood: the nearest dry junction is always the next to get wet. And once a junction is wet, no later route can possibly beat the water that's already there — any other path would have to travel through somewhere at least as far away, and roads only add cost.

Relaxation: the only move you make

Each time you finalize a place u, you look down every road leaving it and ask one question: "Does going through u beat what I had written down?"

That update is called relaxation, and it's the only way the notebook ever improves.

Watch it run, step by step

Same graph, full trace — follow along on the graph below. A ✓ means finalized: the flood has reached it and its number will never change again.

Step 1 — finalize A (cost 0), relax its roads. Reaching B through A costs 0+4; reaching C costs 0+1:

   A:0✓   B:4   C:1   D:∞   E:∞
          via A  via A

Step 2 — the cheapest unfinalized place is C (1). Finalize it, relax its roads. And here's the moment that makes Dijkstra click: going through C reaches B for 1 + 2 = 3, beating the 4 we had written down. Cross it out!

   A:0✓   B:3    C:1✓   D:9   E:∞
          was 4,        via C
          via C!

Step 3 — cheapest unfinalized is B (3). Finalize, relax. Through B, D costs 3 + 5 = 8, beating the 9 via C:

   A:0✓   B:3✓   C:1✓   D:8    E:∞
                        was 9,
                        via B!

Step 4 — finalize D (8), relax. E through D costs 8 + 3 = 11:

   A:0✓   B:3✓   C:1✓   D:8✓   E:11

Step 5 — finalize E (11). Nothing left. Final answer:

   A:0    B:3    C:1    D:8    E:11
 
   cheapest route to E:  A → C → B → D → E   (1 + 2 + 5 + 3 = 11)

Notice the route to E never uses the "direct-looking" roads A→B or C→D. Nobody planned that — it fell out of five repetitions of one rule.

The bookkeeping: a priority queue and one sneaky trick

"Grab the cheapest unfinalized place" screams min-heap: pop the smallest, push improvements, every operation logarithmic.

One wrinkle. When B improved from 4 to 3, a textbook would update B's entry inside the heap (a "decrease-key"). The standard library's PriorityQueue can't do that, so the usual workaround is lazy deletion: don't update — just push a fresh entry and let the old one go stale.

   the heap may briefly hold two entries for B:
 
   heap:  (3, B)   (4, B)
            │        │
            │        └── stale — when popped, B is already finalized
            │            at 3, so we skip it in O(1)
            └─────────── the real one, popped first (smaller)

The stale check is one comparison: if the cost on the entry is worse than what's in the notebook, ignore it. That single if is the difference between a correct implementation and a subtly broken one.

How fast is it, really?

With V places and E roads, every place is popped once and every road can push one entry. Each heap operation costs O(log V), which gives:

How you store the frontier is the whole performance story:

The Fibonacci heap wins on paper, but its constant factors lose to a humble binary heap on any graph you'll actually meet.

The complete implementation

Everything above, in one class — the flood, the notebook, and the lazy-deletion trick:

package dev.fiveyear.graph;
 
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
 
public final class Dijkstra {
 
    /** graph.get(u) = list of {to, weight}; returns shortest distance to every vertex. */
    public static int[] shortestPaths(List<List<int[]>> graph, int source) {
        int[] dist = new int[graph.size()];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;
 
        // min-heap of {distance, vertex}
        PriorityQueue<long[]> heap = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
        heap.add(new long[] {0, source});
 
        while (!heap.isEmpty()) {
            long[] top = heap.poll();
            long d = top[0];
            int u = (int) top[1];
            if (d > dist[u]) {
                continue; // stale entry — already finalized with a smaller distance
            }
 
            for (int[] edge : graph.get(u)) {
                int v = edge[0];
                long nd = d + edge[1];
                if (nd < dist[v]) {
                    dist[v] = (int) nd;
                    heap.add(new long[] {nd, v});
                }
            }
        }
        return dist;
    }
}

And here's our graph from the trace, getting exactly the answers we computed by hand:

List<List<int[]>> graph = new ArrayList<>();
for (int i = 0; i < 5; i++) graph.add(new ArrayList<>());
 
// A=0, B=1, C=2, D=3, E=4
graph.get(0).add(new int[] {1, 4}); // A → B (4)
graph.get(0).add(new int[] {2, 1}); // A → C (1)
graph.get(2).add(new int[] {1, 2}); // C → B (2)
graph.get(1).add(new int[] {3, 5}); // B → D (5)
graph.get(2).add(new int[] {3, 8}); // C → D (8)
graph.get(3).add(new int[] {4, 3}); // D → E (3)
 
int[] dist = Dijkstra.shortestPaths(graph, 0);
// dist = [0, 3, 1, 8, 11]  →  A:0  B:3  C:1  D:8  E:11

Where to go from here

You now own the flood: finalize the nearest, relax its edges, repeat. Three natural next stops, one for each way the assumptions can change:

• Negative edges? The flood breaks — learn Bellman–Ford, which trades speed for tolerance.
• All weights equal? You don't need a heap at all — a plain BFS finds shortest paths in O(V + E).
• Want it faster on maps? A* is Dijkstra plus a compass: a heuristic that pulls the search toward the goal instead of flooding in every direction. It's what real navigation engines build on.

Next time your maps app reroutes you around traffic in half a second, you'll know what just happened: a flood was poured at your blue dot, and you're driving down the path the water found.