Vibe Engines Learn
ALGORITHMS · 01  /  DIJKSTRA'S SHORTEST PATH

The Last Mile.

Every map app, every router, every game's pathfinding runs some flavour of this. But you won't watch it. You'll drive it — lose to your own instincts, then meet the courier who never does.

THE GIST · 20 SECONDS

Dijkstra's algorithm finds the shortest path from a starting point to every other point in a weighted graph — a network where each connection has a cost (here, minutes of traffic). Its one idea: always expand the cheapest-known point first, and the moment you reach a point that way, its shortest distance is locked in forever. That's it. It's how maps route you, how the internet routes packets, and how game characters find their way.

  • Nodean intersection / point
  • Edgea street between two nodes
  • Weightthe cost to cross an edge
  • Frontieropen nodes, cheapest-first (a priority queue)
  • Relaxfound a cheaper route → lower a node's distance
  • Settlelock a node — its distance is now final

① Drive by instinct  →  ② Watch the Dispatcher flood the city  →  ③ Predict the next lock  →  ④ Break it with a negative street

YOUR RUN 0min
Depot Drop-off Street · traffic = minutes
Text version of the city map (for screen readers & keyboard)
UNDER THE HOOD

What you just played, written down

You drove it, watched the flood, and predicted the next lock. Here's the same thing as an algorithm — it should read like subtitles to a movie you've already seen.

How the Dispatcher thinks — five steps

  1. Set distances. The start is 0; every other node is ∞ (unknown).
  2. Open the start. Put it in a priority queue keyed by best-known distance.
  3. Pop the cheapest. Take the open node with the smallest distance — call it current.
  4. Relax neighbours. For each street out of current, if reaching the neighbour through current is cheaper than its best-known distance, lower it.
  5. Settle & repeat. Lock current — its distance is now final — and loop until the queue empties (or you've settled the goal).
WHY IT'S CORRECT

Because no street costs less than zero, the instant a node is popped as the cheapest open node, no other path could ever reach it more cheaply. So its distance is safe to lock. That single guarantee is the whole algorithm — and exactly the law you saw in the game.

The algorithm

function dijkstra(graph, start):
    dist[start] = 0
    for every other node v: dist[v] = ∞
    pq = min-priority-queue seeded with (0, start)

    while pq not empty:
        (d, u) = pq.pop_min()        # cheapest open node
        if u is settled: continue
        settle(u)                    # dist[u] is now final
        for each edge (u → v, w):
            if dist[u] + w < dist[v]:  # relaxation
                dist[v] = dist[u] + w
                prev[v] = u
                pq.push((dist[v], v))

    return dist, prev                # prev rebuilds the path
TIME O((V + E) log V) with a binary-heap queue · V nodes, E edges
SPACE O(V) distances, predecessors, and the queue

Solved by hand — the exact trace for the city above

Every lock in order, with the best-known distance at the moment it settled. This is precisely what the loop above does, run on the map you just played.

⚠ When it breaks

Dijkstra trusts that locking is final — which is only true with non-negative weights. Add a single negative edge and a cheaper path can appear after a node is already settled, quietly corrupting the answer; a negative cycle makes the shortest path undefined (−∞) entirely. (In Act 4 — Break it you make one street pay you and watch a finite-but-wrong answer, then make it pay both ways for the −∞ cycle Dijkstra never notices.)

↔ Its cousins

Bellman-Ford handles negative edges (slower: O(V·E)). Add a goal-direction heuristic and Dijkstra becomes A*, which aims the flood as a beam instead of spreading everywhere. BFS is just Dijkstra when every weight is 1.

★ Where you've used it

Turn-by-turn navigation (Maps), internet routing (OSPF / IS-IS), NPC and unit pathfinding in games, network-latency planning, and plenty of "cheapest way from A to B" puzzles.

RUN IT YOURSELF

Dijkstra's algorithm, in Python & TypeScript

The same shortest-path search in both languages, running for real in your browser — Python via WebAssembly, TypeScript transpiled on the fly. Switch tabs to compare them, read the numbered comments, edit anything, and hit Run (or ⌘/Ctrl + Enter).

HOW TO READ THE CODE — 4 IDEAS
  1. Every node starts at distance infinity, except the source at 0 (step 1).
  2. Repeatedly settle the nearest not-yet-settled node — its distance is now final (step 2).
  3. Relax each edge out of it: if going through it is cheaper, lower the neighbour's distance (step 3).
  4. Once the goal is settled, its distance is the cheapest total cost (step 4). Needs non-negative weights.
CPython · WebAssembly
QUICK CHECK

Did it stick?

FAQ

Dijkstra's algorithm, answered

What is Dijkstra's algorithm?

Dijkstra's algorithm finds the shortest path from one starting node to every other node in a weighted graph with non-negative edge weights. It always expands the closest unvisited node first, locking in each node's shortest distance one at a time. Published by Edsger W. Dijkstra in 1959, it's the backbone of map navigation, network routing and game pathfinding.

How does Dijkstra's algorithm work?

It keeps a tentative distance to every node (0 for the start, ∞ for the rest) in a min-priority queue. It repeatedly pops the closest unsettled node, marks it settled (its distance is now final), and relaxes each neighbour — lowering its distance if the route through the current node is cheaper. This repeats until the queue is empty or the destination is settled. Play Acts 1–3 above to watch it happen.

What is the time complexity of Dijkstra's algorithm?

With a binary-heap priority queue it runs in O((V + E) log V) time (V vertices, E edges). A plain array version is O(V²) — sometimes faster on dense graphs — and a Fibonacci heap reaches O(E + V log V). Space complexity is O(V).

Why doesn't Dijkstra's algorithm work with negative edge weights?

Dijkstra assumes that once a node is settled, no cheaper path to it can ever appear — which is only true when every edge is non-negative. A negative edge can reveal a cheaper route to an already-settled node after the fact, and a negative cycle makes the shortest path undefined (−∞). Use the Bellman-Ford algorithm for negative edges. (Try Act 4 — Break it — to see this happen live.)

What's the difference between Dijkstra's algorithm and BFS?

BFS finds the path with the fewest edges on an unweighted graph using a FIFO queue. Dijkstra finds the lowest-total-weight path on a weighted graph using a priority queue. Dijkstra reduces to BFS when every edge weight is equal — BFS is just the case where all weights are 1.

Is Dijkstra's algorithm greedy or dynamic programming?

It's a greedy algorithm: each step commits to the closest unsettled node and never reconsiders. The non-negative-weight invariant is what makes that greedy choice provably correct.

Dijkstra vs A* — what's the difference?

A* is Dijkstra plus a heuristic that estimates the remaining distance to a single goal, so it steers the search toward the target and settles far fewer nodes. With a zero heuristic, A* is Dijkstra. Use Dijkstra for distances to many destinations; A* for one goal with a good heuristic.

Where is Dijkstra's algorithm used in real life?

Turn-by-turn navigation (Google/Apple Maps), internet routing protocols (OSPF, IS-IS), character and unit pathfinding in games, network traffic engineering, and logistics "cheapest route" problems.

RUN CARD

—

Next world → add a compass and the flood becomes a beam. That's A*.

▶  Watch it explained

Prefer a video walkthrough?

Finished this one? 0 / 99 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

More Algorithms

Explore more from Vibe Engines

Handbooks →
Roadmaps →
System Designs →
AI System Designs →
Labs →
Paper Breakdowns →