Graph Algorithms

How Dijkstra's Algorithm Works

Dijkstra's algorithm finds shortest paths on a weighted graph by always settling the nearest unsettled vertex. Watch why that greedy choice is safe — and why one negative edge breaks it.

4258362435A0B∞C∞D∞E∞F∞G∞H∞
Reached, not settled

Empty.

Settled, cheapest first

Nothing yet.

  • Not reached
  • Waiting
  • Current
  • Finished
Speed

Step 1 of 20

A is 0 away from itself. Everything else starts at infinity.

Counters

Settled
0/8
Reached
1
Cost here
-
Edges
10

Settings

Graph

Dijkstra

  1. 1dist[start] = 0, everything else inf
  2. 2while unsettled nodes remain:
  3. 3 node = closest unsettled node
  4. 4 settle(node)
  5. 5 for each neighbour:
  6. 6 d = dist[node] + weight
  7. 7 if d < dist[neighbour]:
  8. 8 dist[neighbour] = d

What each one answers

AlgorithmWhat it answersTimeNeeds
Breadth-firstFewest hops from the startO(V + E)A queue
Depth-firstReachability, one branch at a timeO(V + E)A stack
Cycle detectionDoes a cycle exist, and whereO(V + E)Node colours
Topological sortA valid order to do the work inO(V + E)No cycles
DijkstraCheapest path by edge weightO(E log V)Non-negative weights

V is the number of nodes and E the number of edges. Switch to the graph with a cycle and the topological sort gets stuck: once a cycle exists there is no valid order.

Complexity

BestAverageWorstExtra memory
O((V + E) log V)O((V + E) log V)O((V + E) log V)O(V)

With a binary heap. A Fibonacci heap gives O(E + V log V) in theory and loses in practice; with weights all equal it degenerates to BFS.

How dijkstra's algorithm works

Dijkstra's algorithm keeps a tentative distance for every vertex and repeatedly settles the unsettled vertex with the smallest one, relaxing its outgoing edges as it goes. The greedy step is safe because all weights are non-negative: no later detour can make a longer path shorter, so the smallest tentative distance cannot be improved by anything still unexplored. A single negative edge destroys exactly that argument, which is why Dijkstra gives wrong answers on negative weights rather than slow ones.

  1. Set the start's distance to zero and every other vertex's to infinity. Push the start onto a min-priority queue.
  2. Pop the vertex with the smallest tentative distance. Its distance is now final.
  3. Relax each outgoing edge: if going through this vertex is cheaper than the neighbour's current distance, update it and push the neighbour.
  4. Skip any popped entry whose distance is stale — a cheaper route to that vertex was already settled.
  5. Stop when the queue empties, or early once the destination is popped.

Implementation

The same algorithm the visualiser is running, written to be read.

import heapq


def dijkstra(graph, start):
    """graph: {node: [(neighbour, weight), ...]} with weights >= 0."""
    distance = {node: float("inf") for node in graph}
    distance[start] = 0
    came_from = {start: None}
    queue = [(0, start)]

    while queue:
        cost, node = heapq.heappop(queue)
        # A cheaper route to this node was already settled.
        if cost > distance[node]:
            continue
        for neighbour, weight in graph[node]:
            candidate = cost + weight
            if candidate < distance[neighbour]:
                distance[neighbour] = candidate
                came_from[neighbour] = node
                heapq.heappush(queue, (candidate, neighbour))

    return distance, came_from

When to use it

  • Use it for shortest paths with non-negative weights: road distances, network latency, transit fares, any cost that cannot be negative.
  • Use it with an early exit when you only need one destination, and with a heuristic — that is A* — when you have one that never overestimates.
  • Avoid it with negative edges. Bellman-Ford handles those and detects negative cycles; Johnson's algorithm reweights a graph so Dijkstra can be used anyway.
  • Note that on an unweighted graph BFS gives the same answer in O(V + E) with no heap at all.

Check yourself

If the animation made sense, these should too.

Why does one negative edge break Dijkstra rather than just slow it down?

Because its greedy step assumes that the smallest tentative distance is final - which holds only if no path can get cheaper by being longer. A negative edge makes exactly that possible, so a settled vertex can turn out to have a shorter route, and the algorithm never revisits it.

Why skip a popped entry whose distance is greater than the recorded one?

Because the same vertex can be pushed several times as cheaper routes are found, and the stale entries stay in the heap. Skipping them is what makes the lazy-deletion version correct; without the check, a vertex gets expanded with an out-of-date distance.

More graph algorithms