Dijkstra's Algorithm: Finding the Shortest Path

Why "fewest turns" can trick you

Imagine you are cycling from home to school. There are three routes. Route 1 has one straight road, 6 km long, but it runs along a busy highway with a steep climb, so in terms of a map it looks like "just one edge." Route 2 has three smaller roads that add up to 4 km total. If someone asked you "which route has fewer roads to turn onto," Route 1 wins — it is a single road. But if someone asked "which route gets you to school fastest," Route 2 wins, because 4 km of riding is less than 6 km, regardless of how many turns you take.

This is the exact trap that trips up students meeting shortest-path problems for the first time. An algorithm like Breadth-First Search (BFS), which you may have already studied, finds the path with the fewest edges between two points in a graph. That is perfect when every road, every hop, every connection costs the same "one step." But real roads have different lengths. Real flights have different durations. Real network links have different latencies. The moment edges carry different weights, "fewest edges" and "shortest total distance" stop being the same question, and BFS silently gives you the wrong answer to the second one.

Dijkstra's algorithm, published by the Dutch computer scientist Edsger W. Dijkstra in 1959, is the classical solution to this exact problem: given a graph where every edge has a non-negative weight (a distance, a cost, a time), find the minimum total-weight path from one starting vertex to every other vertex.

From map to graph: naming the pieces precisely

Before formalizing anything, let's agree on vocabulary using the cycling example. Each place you can stand (your home, an intersection, your school) is a vertex (also called a node). Each road connecting two places is an edge. The length of that road, in kilometres, is the edge's weight. A path from home to school is any sequence of edges that connects them, and the path length is simply the sum of the weights of the edges you used — not the number of edges.

So the single question Dijkstra's algorithm answers is: starting from one fixed vertex (call it the source), what is the minimum possible sum of edge weights needed to reach every other vertex in the graph?

The greedy idea behind Dijkstra

Here is the core insight, stated in plain language first: if you always finalize the distance of whichever unvisited place is currently closest to the source, you can never later discover a shorter way to reach it. Once you commit to "the closest remaining place is X, and its distance is d," that distance is guaranteed correct, provided no edge weight is negative.

Why does that guarantee hold? Suppose X is the closest unvisited vertex right now, at distance d. Any other path to X that goes through some other unvisited vertex Y must first reach Y. But every unvisited vertex, including Y, is at distance ≥ d (that's what "X is the closest remaining" means). Since edge weights can't be negative, continuing from Y to X can only add more distance, never subtract. So no detour through an unvisited vertex can ever beat d. This is precisely why Dijkstra's algorithm is called a greedy algorithm — at every step it makes the locally best choice (pick the nearest unvisited vertex), and that local choice turns out to be globally correct.

This also tells you exactly where the algorithm can break: if an edge weight were negative, "continuing can only add distance" would no longer be true, and the greedy guarantee collapses. We'll see a concrete example of that failure later in this chapter.

The algorithm, step by step

Dijkstra's algorithm maintains two things for every vertex: a tentative distance from the source (starting at infinity for everyone except the source itself, which starts at 0), and whether the vertex is finalized (its shortest distance is confirmed and will never change again).

1. Set the source's distance to 0, and every other vertex's distance to infinity. No vertex is finalized yet.
2. Repeat: among all vertices not yet finalized, pick the one with the smallest tentative distance. Finalize it.
3. For every neighbour of the vertex you just finalized, check whether reaching it through the vertex you just finalized would be shorter than its current tentative distance. This check — "current distance to the finalized vertex, plus the weight of the edge to the neighbour" — is called relaxation. If it's shorter, update the neighbour's tentative distance.
4. Stop when every vertex is finalized (or when the destination you care about has been finalized, if you only need one target).

Doing step 2 efficiently — "find the smallest tentative distance among many candidates, repeatedly" — is exactly what a min-heap priority queue is built for, which is why real implementations use one, as you'll see in the code below.

Worked example: routing through six junctions

Let's trace the algorithm by hand on a small road network of six junctions, A through F, with distances in kilometres marked on each road. A is where we start.

The green edges are the ones the algorithm ends up actually using for its shortest paths — this is called the shortest-path tree. The grey edges exist in the road network but never turn out to be part of the cheapest route from A. Let's now trace, one finalized vertex at a time, exactly how the algorithm arrives at this picture.

Step 1: Finalize A (dist 0).
  Relax neighbours: B -> 0+4 = 4   C -> 0+1 = 1
  Tentative: A=0(done) B=4 C=1 D=inf E=inf F=inf

Step 2: Smallest unfinalized = C (1). Finalize C.
  Relax neighbours of C:
    B -> 1+2 = 3   (3 < 4, update B)
    D -> 1+8 = 9   (9 < inf, update D)
    E -> 1+4 = 5   (5 < inf, update E)
  Tentative: A=0 B=3 C=1(done) D=9 E=5 F=inf

Step 3: Smallest unfinalized = B (3). Finalize B.
  Relax neighbours of B:
    D -> 3+5 = 8   (8 < 9, update D)
  Tentative: A=0 B=3(done) C=1 D=8 E=5 F=inf

Step 4: Smallest unfinalized = E (5). Finalize E.
  Relax neighbours of E:
    D -> 5+2 = 7   (7 < 8, update D)
    F -> 5+3 = 8   (8 < inf, update F)
  Tentative: A=0 B=3 C=1 D=7 E=5(done) F=8

Step 5: Smallest unfinalized = D (7). Finalize D.
  Relax neighbours of D:
    F -> 7+6 = 13  (13 is NOT < 8, no update)
  Tentative: D=7(done), F stays 8

Step 6: Smallest unfinalized = F (8). Finalize F. No unfinalized neighbours left.

Final shortest distances from A:
  A=0  C=1  B=3  E=5  D=7  F=8

Notice the moment in Step 5 that matters most for understanding why this works: D tries to relax F via the direct D–F road (weight 6), giving 7+6=13. But F was already finalized at 8, reached earlier via A→C→E→F. Because D's own distance (7) was already larger than F's finalized distance (8) by the time D got processed, that 13 could never have won. This is the greedy guarantee from the previous section playing out in numbers: once a vertex is finalized, nothing still-unfinalized can undercut it, because every remaining road can only add distance, never subtract it.

Also notice something students often miss: the shortest route from A to F is A→C→E→F, using three roads and totaling 1+4+3=8 km — not the direct-looking route through B and D, and not "whichever route has the fewest roads." This is the "fewest turns" trap from the opening example, now proven with real numbers.

Recovering the actual route, not just its length

The trace above gives distances, but usually you also want to know which roads to take. The fix is simple: every time you relax an edge successfully (i.e., you update a neighbour's distance), also record which vertex you relaxed it from. This is called a predecessor pointer. For our graph: B's predecessor is C, C's predecessor is A, D's predecessor is E, E's predecessor is C, F's predecessor is E. To read off the route to any vertex, just follow predecessors backward to the source: F ← E ← C ← A, then reverse it to get A → C → E → F.

Implementing it: Python with a min-heap

A naive implementation that scans all vertices to find the minimum tentative distance at every step works, but it's slow for large graphs. Real implementations use Python's heapq module as a min-heap priority queue, so "find the closest unfinalized vertex" takes only O(log V) time instead of O(V).

import heapq

def dijkstra(graph, source):
    distances = {node: float('inf') for node in graph}
    distances[source] = 0
    visited = set()
    pq = [(0, source)]          # (distance, vertex)

    while pq:
        current_dist, current_node = heapq.heappop(pq)
        if current_node in visited:
            continue             # a stale, already-finalized entry
        visited.add(current_node)

        for neighbor, weight in graph[current_node]:
            if neighbor in visited:
                continue
            new_dist = current_dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))

    return distances

graph = {
    'A': [('B', 4), ('C', 1)],
    'B': [('A', 4), ('C', 2), ('D', 5)],
    'C': [('A', 1), ('B', 2), ('D', 8), ('E', 4)],
    'D': [('B', 5), ('C', 8), ('E', 2), ('F', 6)],
    'E': [('C', 4), ('D', 2), ('F', 3)],
    'F': [('D', 6), ('E', 3)],
}

print(dijkstra(graph, 'A'))
# {'A': 0, 'B': 3, 'C': 1, 'D': 7, 'E': 5, 'F': 8}

Trace this against Step-2 and Step-3 of the hand trace above and you'll see the code push several entries for the same vertex into the heap — for instance, B is pushed once as (4, 'B') when A is processed, and again as (3, 'B') when C is processed. That's normal and deliberate: rather than searching the heap to find and update an old entry (which heaps aren't built for), the code just pushes a fresh, better one. When the stale (4, 'B') eventually rises to the top of the heap, the line if current_node in visited: continue notices 'B' was already finalized and simply throws that stale entry away. This trick is called lazy deletion, and it's what makes the heap-based version both simple to write and efficient to run.

Why the greedy choice needs non-negative weights

Let's directly test the claim from earlier that negative edge weights break Dijkstra's algorithm, using a tiny three-vertex directed example: A→B with weight 2, A→C with weight 4, and C→B with weight −3.

Run the algorithm: start at A (distance 0). Relax A's edges: B becomes 2, C becomes 4. The smallest unfinalized vertex is B at 2, so Dijkstra finalizes B with distance 2 and moves on — B has no outgoing edges to relax. Next, C is finalized at 4. Relaxing C's edge to B gives 4+(−3)=1, which is smaller than B's finalized distance of 2 — but B is already finalized, so the algorithm (correctly, by its own rules) refuses to touch it again.

Dijkstra reports dist(B) = 2. But the real shortest path is A→C→B, with total weight 4+(−3) = 1, which is genuinely shorter. Dijkstra gave the wrong answer, and it did so honestly, following its own rules perfectly — the rules themselves assumed no edge could ever make a path cheaper "after the fact," and a negative weight broke that assumption. This is precisely why textbooks and CBSE questions will state the precondition explicitly: Dijkstra's algorithm requires all edge weights to be non-negative. Graphs with negative edges need a different algorithm (the Bellman–Ford algorithm), which is slower but tolerates negative weights, as long as there's no negative-weight cycle.

Common confusion: Dijkstra vs. Prim's algorithm

If you've studied minimum spanning trees, Dijkstra's algorithm will look suspiciously familiar to Prim's algorithm — both are greedy, both grow a tree one vertex at a time, both use a priority queue to pick "the next vertex to add." Students very commonly mix them up. The difference is in exactly what number the priority queue is sorting by.

Prim's algorithm sorts by the weight of the single edge connecting a candidate vertex to the tree already built — it is answering "which next edge is individually cheapest?" Dijkstra's algorithm sorts by the total accumulated distance from the source — it is answering "which vertex is closest to the source overall?"

Here's a compact example where they diverge. Take three vertices A, B, C with roads A–B (weight 10), A–C (weight 10), and B–C (weight 1). Prim's algorithm, starting from A, first adds the cheapest available edge — say A–B (10) — then looks for the cheapest edge connecting the tree {A,B} to the rest: B–C at weight 1 beats A–C at weight 10, so it adds B–C. Prim's tree is A–B–C, with the path from A to C running through B, total 10+1=11.

Dijkstra's algorithm, finding shortest paths from A, computes dist(B)=10 (direct edge) and dist(C) = min(10 direct, 10+1 via B) = 10, choosing the direct A–C edge. Dijkstra's tree uses A–C directly, distance 10 — not 11. Prim's tree minimizes the total wood used to connect all three houses; Dijkstra's tree minimizes the distance from A to each house individually. A minimum spanning tree is not, in general, a shortest-path tree, even though the two algorithms look almost identical in code.

Complexity: why the heap matters

With V vertices and E edges, a version of Dijkstra's algorithm that scans all unfinalized vertices to find the minimum every time takes O(V) per step, repeated V times, giving O(V²) — fine for a few hundred junctions, painfully slow for a graph with millions of vertices, like a national road network. Using a binary min-heap, extracting the minimum costs O(log V), and it happens at most once per edge relaxation (since each relaxation may push a new heap entry), giving a total of O((V+E) log V). For a sparse graph (roads, where each junction connects to only a handful of others, rather than to every other junction), E is much closer to V than to V², so the heap version is dramatically faster — this is exactly why every practical shortest-path implementation, from mapping software to network routers, uses a priority queue rather than a plain scan.

Where this shows up

Dijkstra's algorithm (or a close relative of it) is not a textbook curiosity — it is running, right now, underneath systems you likely use. Internet routers running the OSPF protocol (Open Shortest Path First) use Dijkstra's algorithm directly to compute the shortest path a data packet should take across a network of routers, where edge weights represent link cost. Turn-by-turn navigation apps use an optimized descendant of Dijkstra's algorithm called A* (A-star), which adds a smart estimate of remaining distance to guide the search toward the destination faster, but the core relax-and-finalize logic is exactly what you traced by hand in this chapter. Indian Railways' own route and fare systems, when computing the shortest route in kilometres between two stations across a network of thousands of track segments, are solving the identical shortest-path problem you just solved for six junctions — just with far more vertices and edges.

Check yourself

• In the six-junction graph, what is the shortest distance from A to D, and which junctions does the route pass through? (Trace it yourself before checking: the answer is in Step 5's table, and the predecessor chain in the "recovering the route" section.)
• Suppose a new road is added directly from A to F with weight 9. Does the shortest-path tree computed in this chapter change, and if so, how?
• Explain in your own words why, at the moment a vertex is popped from the priority queue for the first time, its tentative distance is guaranteed to be its true shortest distance — and why that argument stops working the instant one edge weight is allowed to be negative.
• Given the star example (A–B=10, A–C=10, B–C=1), compute Prim's minimum spanning tree total weight and Dijkstra's total shortest-path weight to C, and explain in one sentence why they differ.

Summary

Dijkstra's algorithm finds the shortest total-weight path from a single source to every other vertex in a graph with non-negative edge weights. It works by repeatedly finalizing the closest not-yet-finalized vertex and relaxing its outgoing edges — updating a neighbour's tentative distance whenever a cheaper route through the newly finalized vertex is discovered. This greedy strategy is provably correct only because non-negative weights guarantee that continuing along any path can never decrease its total cost; feed the algorithm a negative edge and it can confidently report a wrong answer. Implemented with a min-heap priority queue and lazy deletion of stale entries, it runs in O((V+E) log V) time, which is why it is the practical backbone of internet routing (OSPF), mapping software (via the A* variant), and any system — including railway route planning — that needs the genuinely shortest path through a network, not merely the path with the fewest hops.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where dijkstra's algorithm: finding the shortest path is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting dijkstra's algorithm: finding the shortest path to at least 3 other topics you have studied.