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 a single negative edge breaks it.

Reached, not settled

Empty.

Settled, cheapest first

Nothing yet.

Not reached
Waiting
Current
Finished

1/20

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

Counters

Settled: 0/8
Reached: 1
Cost here: -
Edges: 10

Settings

Graph

More options

Start fromA

Dijkstra

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

What each one answers

Algorithm	What it answers	Time	Needs
Breadth-first	Fewest hops from the start	O(V + E)	A queue
Depth-first	Reachability, one branch at a time	O(V + E)	A stack
Cycle detection	Does a cycle exist, and where	O(V + E)	Node colours
Topological sort	A valid order to do the work in	O(V + E)	No cycles
Dijkstra	Cheapest path by edge weight	O(E log V)	Non-negative weights

Scroll the table sideways for the rest of the columns.

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

Best	Average	Worst	Extra 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.

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

Implementation

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. Add a heuristic that never overestimates and you have A*.
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.

The visualiser uses a binary heap, which is what you would actually write. A Fibonacci heap brings the bound down to O(E + V log V) and is the version textbooks quote, but its constants are bad enough that it loses on the graph sizes most people have. Worth knowing the distinction exists, and worth not reaching for it.

Check yourself

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?