Dijkstra's algorithm visualizer
Dijkstra's algorithm finds the shortest path from one node to every other node in a weighted graph. Pick a start and a target below and step through it: each step either settles the closest node or relaxes one edge. Further down: a worked example table, code, complexity, and why a negative weight breaks it.
settled in the queue best way found so far shortest path to F edge being relaxed
Shortest path from A to F: A → C → B → D → E → F, total 12.
| Node | Distance | Previous | State |
|---|---|---|---|
| A | 0 | – | settled |
| B | 3 | C | settled |
| C | 2 | A | settled |
| D | 8 | B | settled |
| E | 10 | D | settled |
| F | 12 | E | settled |
How to use the simulator
The numbers on the edges are weights, such as distances or travel times. The number above each node is its current best known distance from the start. Press Step from the start and keep pressing Next step: the algorithm alternates between taking the closest node out of the priority queue (it becomes settled, drawn filled) and relaxing each edge out of that node. The table on the right shows every node's distance and the node it was reached from; at the end, following the "previous" column back from the target gives the shortest path.
Things to try:
- On the six-node graph, the direct edge A–B weighs 4, but the path A–C–B weighs 3. Watch B's distance drop when C is settled.
- Change a weight and watch the path move. Set C–E to 1 and the route to F changes.
- Load A negative edge. Dijkstra settles B at distance 1 before it discovers the path through C, which costs −1, and the panel shows Bellman-Ford's correct answer next to it.
The simulator visits neighbours in alphabetical order and breaks ties between equal distances alphabetically, so its steps match hand-worked textbook solutions. Its distances were checked against Bellman-Ford on 2,000 random weightings of the two non-negative graphs, from every start node, with no differences.
What is Dijkstra's algorithm?
Dijkstra's algorithm finds the shortest paths from a single start node to every other node in a graph whose edges have non-negative weights. The weights can stand for anything that adds up along a path: kilometres, minutes, link costs, prices. The result is a distance for every node and a shortest-path tree: for each node, the previous node on its best path from the start.
The algorithm grows a set of settled nodes whose shortest distance is known. At each step it settles the unsettled node with the smallest tentative distance, then checks whether going through that node gives any of its neighbours a shorter distance. It stops when every reachable node is settled, or earlier if only one target matters and the target has been settled.
How Dijkstra's algorithm works
- Set the start node's distance to 0 and every other node's to infinity. Put the start node in a priority queue.
- Take the node u with the smallest distance out of the queue. Its distance is now final: it is settled.
- For each edge from u to a neighbour v with weight w, relax the edge: if dist(u) + w is less than dist(v), set dist(v) to that value, record u as v's previous node, and put v in the queue (or lower its key there).
- Repeat from step 2 until the queue is empty.
Why is a node's distance final when it leaves the queue? Every other path to it would have to leave the settled set through some node still in the queue, and that node is already at least as far away. With no negative edges, the rest of that path cannot make it shorter. This one argument is the whole proof, and it is also exactly what fails when a weight is negative.
Dijkstra's algorithm example, step by step
The six-node graph from the simulator, starting at A. Its undirected edges are A–B (4), A–C (2), B–C (1), B–D (5), C–D (8), C–E (10), D–E (2), D–F (6), E–F (2). Each row shows the node settled in that iteration and every distance after relaxing its edges; a ✓ marks distances that are final.
| Iteration | Settled | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|
| 0 | – | 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
| 1 | A | 0 ✓ | 4 | 2 | ∞ | ∞ | ∞ |
| 2 | C | 0 ✓ | 3 | 2 ✓ | 10 | 12 | ∞ |
| 3 | B | 0 ✓ | 3 ✓ | 2 ✓ | 8 | 12 | ∞ |
| 4 | D | 0 ✓ | 3 ✓ | 2 ✓ | 8 ✓ | 10 | 14 |
| 5 | E | 0 ✓ | 3 ✓ | 2 ✓ | 8 ✓ | 10 ✓ | 12 |
| 6 | F | 0 ✓ | 3 ✓ | 2 ✓ | 8 ✓ | 10 ✓ | 12 ✓ |
The shortest path from A to F is A → C → B → D → E → F, with length 12. Note iteration 2: B's distance was 4 through the direct edge, and settling C, at distance 2, lowered it to 3 through the edge C–B of weight 1. Following the previous-node pointers back from F rebuilds the path: F ← E ← D ← B ← C ← A.
Dijkstra's algorithm in Python
Python's heapq module has no decrease-key operation, so the usual implementation pushes a new entry whenever a distance improves and skips entries that are out of date when they come off the heap. This is called lazy deletion.
import heapq
def dijkstra(graph, source):
# graph: {node: {neighbour: weight, ...}, ...}, weights >= 0
dist = {node: float('inf') for node in graph}
prev = {node: None for node in graph}
dist[source] = 0
heap = [(0, source)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue # stale entry: u was already reached more cheaply
for v, w in graph[u].items():
if d + w < dist[v]:
dist[v] = d + w
prev[v] = u
heapq.heappush(heap, (dist[v], v))
return dist, prev Run on the six-node graph from A, this returns the same distances as the table above: A = 0, B = 3, C = 2, D = 8, E = 10, F = 12. The heap can hold up to E entries instead of V, which changes the bound to O(E log E), the same as O(E log V) since E is at most V².
Time complexity
Dijkstra's algorithm performs V extract-min operations and up to E decrease-key operations (one per relaxation that improves a distance), so its running time depends on the priority queue:
| Priority queue | Running time | Best for |
|---|---|---|
| Unsorted array | O(V²) | Dense graphs, where E is close to V²; Dijkstra's original version |
| Binary heap | O((V + E) log V) | Sparse graphs, such as road networks; the usual choice |
| Fibonacci heap | O(E + V log V) | The best bound in theory (Fredman and Tarjan, 1984), rarely the fastest in practice |
Space is O(V) for the distances and previous nodes, plus the queue. For a single target, stopping as soon as the target is settled can save a great deal of work, though the worst case is unchanged.
Why Dijkstra fails with negative weights
The simulator's third graph is directed, with edges A→B (1), A→C (2), C→B (−3) and B→D (2). Dijkstra settles A, then B at distance 1, because 1 is smaller than C's 2, then D at 3. When it finally settles C and relaxes C→B, B is already settled, so the cheaper path A→C→B, with length −1, is never used. Dijkstra reports B = 1 and D = 3; the correct answers, from Bellman-Ford, are B = -1 and D = 1.
Allowing settled nodes to be updated again does not fix it in general; it turns the algorithm into something closer to Bellman-Ford, which relaxes every edge V − 1 times and runs in O(VE). Bellman-Ford also detects negative cycles, where no shortest path exists. Johnson's algorithm reweights all edges to be non-negative using one Bellman-Ford run, then uses Dijkstra from every node, which is efficient for all-pairs shortest paths on sparse graphs.
Adding a constant to every weight to make them all positive does not work either: it favours paths with fewer edges, so it can change which path is shortest.
Dijkstra vs BFS, A* and Bellman-Ford
| Algorithm | Weights | Time | Use when |
|---|---|---|---|
| Breadth-first search | All equal | O(V + E) | Every edge costs the same, such as moves on a grid |
| Dijkstra | Non-negative | O((V + E) log V) | Shortest paths from one start, general weights |
| A* | Non-negative | Depends on the heuristic | One start and one target with a good distance estimate, such as maps and games |
| Bellman-Ford | Any, no negative cycles | O(VE) | Negative weights, or detecting negative cycles; distance-vector routing |
| Floyd-Warshall | Any, no negative cycles | O(V³) | All pairs on small, dense graphs |
Where Dijkstra's algorithm is used
- Network routing. Link-state routing protocols, OSPF (RFC 2328) and IS-IS, flood every router's view of its links to all routers in an area. Each router then runs Dijkstra's algorithm, which the OSPF specification calls the shortest path first (SPF) calculation, with itself as the start to build its routing table.
- Maps and navigation. Plain Dijkstra is too slow for a continent's road network on every query, so route planners preprocess the graph. Contraction hierarchies (Geisberger and others, 2008) add shortcut edges so that a query explores only a tiny part of the graph; open-source routers such as OSRM use them.
- Games and robotics, mostly through A*, which is Dijkstra guided by a distance estimate.
- Anywhere costs add up along a path: currency conversion with logarithms of rates, word ladders, dependency costs, network latency maps.
History
Edsger W. Dijkstra designed the algorithm in 1956 at the Mathematical Centre in Amsterdam, to demonstrate the new ARMAC computer with a problem non-specialists could understand: the shortest route between two Dutch cities. In a 2001 interview he recalled working it out in about twenty minutes, without pencil and paper, while sitting at a café terrace with his fiancée. He published it in 1959 in a three-page paper, "A note on two problems in connexion with graphs", in Numerische Mathematik; the other problem in the paper is the minimum spanning tree.
Dijkstra in coding interviews
Dijkstra comes up whenever a problem asks for the cheapest route with weighted steps. Typical examples are LeetCode 743 (Network Delay Time), 1514 (Path with Maximum Probability, where products replace sums and the largest value wins) and 1631 (Path With Minimum Effort, on a grid). Points interviewers look for:
- Building an adjacency list, and choosing a heap over a sorted list.
- Skipping stale heap entries, or keeping a settled set, so nodes are not processed twice.
- Stopping early when only one target matters.
- Knowing when not to use it: BFS when every edge costs the same, Bellman-Ford when weights can be negative, and a modified search with the number of steps in the state when the path length is limited, as in LeetCode 787 (Cheapest Flights Within K Stops).
Dijkstra's algorithm questions and answers
What is Dijkstra's algorithm?
Dijkstra's algorithm finds the shortest paths from one starting node to every other node in a graph whose edge weights are not negative. It repeatedly takes the unsettled node with the smallest known distance, marks that distance as final, and updates the distances of its neighbours. Edsger W. Dijkstra designed it in 1956 and published it in 1959.
What is the time complexity of Dijkstra's algorithm?
With a binary heap as the priority queue it runs in O((V + E) log V) time for V nodes and E edges. With a plain array it is O(V²), which is better for dense graphs. With a Fibonacci heap it is O(E + V log V), though binary heaps are usually faster in practice.
Why doesn't Dijkstra's algorithm work with negative weights?
Dijkstra assumes that once a node is taken from the queue, no later path can reach it more cheaply, because every remaining path is at least as long and edges only add to it. A negative edge breaks that assumption: a path through a node settled later can come back to an earlier node more cheaply, and Dijkstra never revisits it. Bellman-Ford handles negative weights.
What is the difference between Dijkstra's algorithm and BFS?
Breadth-first search finds shortest paths when every edge has the same weight, by exploring nodes in order of the number of edges from the start. Dijkstra's algorithm generalises this to different non-negative weights, using a priority queue ordered by distance instead of a plain queue. On a graph where every edge weighs 1, the two visit nodes in the same order.
What is the difference between Dijkstra and A*?
A* is Dijkstra's algorithm with a heuristic: it orders the queue by distance so far plus an estimate of the distance remaining to the target, such as the straight-line distance on a map. With an estimate that never overestimates, it still finds the shortest path but explores far fewer nodes. Dijkstra is A* with an estimate of zero.
Does Dijkstra's algorithm work on undirected graphs?
Yes. Treat each undirected edge as two directed edges with the same weight. Negative weights are never allowed in an undirected graph, because a negative edge used back and forth is a negative cycle.
Is Dijkstra's algorithm greedy?
Yes. At every step it commits to the closest unsettled node and never reconsiders it. The greedy choice is correct because, with non-negative weights, no path discovered later can be shorter than the one already found to that node.
Where is Dijkstra's algorithm used?
Link-state routing protocols such as OSPF and IS-IS run it on each router to build routing tables. Map and navigation services use it, usually with preprocessing such as contraction hierarchies to answer queries on continental road networks in milliseconds. It also appears in network analysis, game pathfinding (as the basis of A*) and many interview problems.
Further reading
- Dijkstra, 1959A note on two problems in connexion with graphsThe original three-page paper.
- Communications of the ACM, 2010An interview with Edsger W. DijkstraDijkstra's own account of designing the algorithm in twenty minutes.
- RFC 2328, 1998OSPF Version 2Section 16 describes the shortest-path calculation every router runs.
- Sedgewick and WayneAlgorithms, 4th edition: Shortest PathsDijkstra, Bellman-Ford and edge relaxation, with Java code.
- SemicolonyA* search simulatorThe same algorithm with a heuristic pointing towards the target.