When a maps app plans your route from Lahore to Islamabad, or a network router decides where to send a data packet, it is solving a shortest path problem on a graph. The most famous method for this is Dijkstra's algorithm, devised in 1956 by the Dutch computer scientist Edsger Dijkstra. It is simple enough to run by hand in an exam, yet powerful enough to drive real navigation systems.
Graphs, Weights and Paths
A graph \(G = (V, E)\) is a set of vertices (nodes) \(V\) joined by edges \(E\). In a weighted graph, each edge carries a number such as a distance, travel time or cost. A path is a sequence of edges joining one vertex to another, and its length is the sum of its edge weights. The single-source shortest path problem asks: from a starting vertex \(s\), what is the shortest path to every other vertex?
Simply listing every path is hopeless: the number of possible paths can grow exponentially with the number of vertices. Dijkstra's algorithm avoids this with a greedy strategy.
The Key Idea
Dijkstra's algorithm maintains a tentative distance \(d(v)\) for every vertex, starting with \(d(s) = 0\) and \(d(v) = \infty\) for all others. It then repeats:
- Choose the unvisited vertex \(u\) with the smallest tentative distance and mark it visited. Its distance is now final.
- Relax each edge \((u, v)\) with weight \(w\): if \(d(u) + w < d(v)\), update \(d(v) = d(u) + w\) and record \(u\) as the predecessor of \(v\).
The algorithm stops when every vertex has been visited. The relaxation rule is just the triangle inequality in action: going through \(u\) is only worthwhile if it is shorter than the best route known so far.
Why is the greedy choice safe?
Suppose \(u\) has the smallest tentative distance among unvisited vertices. Any other route to \(u\) must leave the visited set through some unvisited vertex \(x\) with \(d(x) \geq d(u)\), and then continue along edges of non-negative weight. So that route has length at least \(d(u)\), and no shorter route can exist. This argument depends entirely on weights being non-negative, which is the algorithm's one essential requirement.
Worked Example 1: A Full Trace
Consider an undirected graph with six vertices A to F and these edges:
- 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: 3
Find the shortest distance from A to every vertex.
Initialisation: \(d(A) = 0\); \(d(B) = d(C) = d(D) = d(E) = d(F) = \infty\).
Iteration 1: visit A (distance 0).
- Relax A–B: \(0 + 4 = 4 < \infty\), so \(d(B) = 4\), predecessor A.
- Relax A–C: \(0 + 2 = 2 < \infty\), so \(d(C) = 2\), predecessor A.
Iteration 2: visit C (distance 2), the smallest unvisited.
- Relax C–B: \(2 + 1 = 3 < 4\), so \(d(B) = 3\), predecessor C. A cheaper route to B has been found.
- Relax C–D: \(2 + 8 = 10\), so \(d(D) = 10\), predecessor C.
- Relax C–E: \(2 + 10 = 12\), so \(d(E) = 12\), predecessor C.
Iteration 3: visit B (distance 3).
- Relax B–D: \(3 + 5 = 8 < 10\), so \(d(D) = 8\), predecessor B.
Iteration 4: visit D (distance 8).
- Relax D–E: \(8 + 2 = 10 < 12\), so \(d(E) = 10\), predecessor D.
- Relax D–F: \(8 + 6 = 14 < \infty\), so \(d(F) = 14\), predecessor D.
Iteration 5: visit E (distance 10).
- Relax E–F: \(10 + 3 = 13 < 14\), so \(d(F) = 13\), predecessor E.
Iteration 6: visit F (distance 13). No further improvements.
Final results:
| Vertex | Shortest distance | Predecessor |
|---|---|---|
| A | 0 | none |
| B | 3 | C |
| C | 2 | A |
| D | 8 | B |
| E | 10 | D |
| F | 13 | E |
Reconstructing the path to F: follow predecessors backwards: F ← E ← D ← B ← C ← A. So the shortest path is A → C → B → D → E → F with length
$$ 2 + 1 + 5 + 2 + 3 = 13 $$
Sanity check: the obvious-looking direct options are longer. A → C → E → F costs \(2 + 10 + 3 = 15\), and A → B → D → F costs \(4 + 5 + 6 = 15\). The winning path uses five edges, showing that fewer edges does not mean a shorter route.
Worked Example 2: Why Negative Weights Break It
Take a directed graph with edges S → A (weight 2), S → B (weight 5) and B → A (weight \(-4\)).
Step 1: Visit S. Set \(d(A) = 2\) and \(d(B) = 5\).
Step 2: Visit A (smallest, distance 2). A is now marked final with distance 2.
Step 3: Visit B (distance 5). Relaxing B → A would give \(5 + (-4) = 1 < 2\), but A is already finalised, so standard Dijkstra never corrects it.
The true shortest distance to A is 1, via S → B → A, but Dijkstra reports 2. With negative edges, the greedy argument fails because a longer-looking route can later become cheaper. For such graphs we use the Bellman–Ford algorithm, which relaxes every edge \(|V| - 1\) times and can also detect negative cycles, at a cost of \(O(|V| \cdot |E|)\) time.
How Fast Is Dijkstra's Algorithm?
The running time depends on how we find the minimum-distance vertex.
- Simple array: scanning for the minimum takes \(O(|V|)\) each time, done \(|V|\) times, giving \(O(|V|^2)\). This is best for dense graphs.
- Binary heap (priority queue): each extraction and each distance update costs \(O(\log |V|)\), giving
$$ O\big((|V| + |E|) \log |V|\big) $$
For a road network with a million junctions and about three million road segments, the heap version needs roughly \(4 \times 10^6 \times 20 = 8 \times 10^7\) basic operations, which a modern computer handles in well under a second. The array version would need about \(10^{12}\).
Where Shortest Paths Are Used
- Navigation: apps use Dijkstra's algorithm or faster variants such as A* search, which adds a straight-line distance estimate to steer the search towards the goal.
- Internet routing: the OSPF protocol runs Dijkstra's algorithm inside routers to build forwarding tables.
- Logistics: delivery companies compute cheapest routes between warehouses.
- Games: characters find their way around maps using A*.
Did You Know?
- Dijkstra said he designed the algorithm in about twenty minutes while sitting at a café terrace in Amsterdam with his fiancée, without pencil and paper.
- He first used it to demonstrate a new computer, the ARMAC, by finding routes between 64 Dutch cities.
- Dijkstra's original 1959 paper is under three pages long, yet it is one of the most cited papers in computer science.
Key Takeaways
- Dijkstra's algorithm finds shortest paths from one source when all edge weights are non-negative.
- It repeatedly finalises the closest unvisited vertex and relaxes its edges.
- Storing predecessors lets you reconstruct the actual path, not just its length.
- With a binary heap it runs in \(O((|V| + |E|) \log |V|)\) time.
- Negative edge weights require Bellman–Ford instead.
Need a graph algorithm traced step by step or help with a data structures assignment? Amathify's experts and PhD scholars are ready to help via WhatsApp or the Ask a Question form.
Stuck on a problem or assignment?
Our experts and PhD scholars solve maths, physics and chemistry — step by step.