Dijkstra's Algorithm: How It Finds the Lowest-Cost Paths

Dijkstra’s algorithm finds the cheapest path from one starting vertex to every reachable vertex in a weighted graph, provided that every edge weight is non-negative. This explanation begins with the distance table and the rule that drives the algorithm. The priority queue and Python implementation come later because they are ways to execute the algorithm efficiently, not the idea that makes it correct.

The Problem Dijkstra Solves

Dijkstra solves a single-source shortest-path problem. Given one starting vertex, it finds the minimum total edge weight needed to reach every vertex that can be reached from that start.

The goal is minimum total weight, not the fewest edges. For example:

A -> B costs 100
A -> C costs 1
C -> B costs 1

The one-edge path A -> B costs 100, while the two-edge path A -> C -> B costs 2. A path with more edges can therefore be cheaper.

The Distance Table

Dijkstra maintains one distance value for each vertex. At the beginning, the start has distance 0. Every other vertex has distance infinity because the algorithm has not discovered a route to it yet.

The meaning of a value depends on whether its vertex is still tentative or has been finalized.

Tentative Distance

A tentative distance is the cheapest path discovered so far. It may still decrease when the algorithm discovers a better route.

Suppose the algorithm first discovers the direct edge A -> B with cost 4. The tentative distance to B becomes 4. If it later discovers A -> C -> B with costs 2 + 1, the tentative distance to B decreases from 4 to 3.

Only an unfinalized vertex has a tentative distance that may change. Once a vertex has been finalized, Dijkstra’s non-negative-edge guarantee says that its distance will not change.

Finalized Distance

A finalized distance has been proven to be the true shortest-path distance from the start. It will no longer change.

This distinction prevents a common mistake. Discovering a route to a vertex does not immediately prove that the route is optimal. The value remains tentative until the algorithm selects that vertex under the rule below.

The One Rule to Remember

When all edge weights are non-negative, the unfinalized vertex with the smallest tentative distance can be safely finalized.

This is enough to run the algorithm even before studying the proof. Use it as the main operating rule:

1. Look at all reachable, unfinalized vertices with known tentative distances.
2. Choose the one with the smallest tentative distance.
3. Finalize it.
4. Check its outgoing edges.
5. Update a neighbor only when the route through the selected vertex is cheaper.
6. Repeat while a reachable, unfinalized vertex remains.

The reason this rule is safe is explained after the example. On a first reading, it is reasonable to use the rule first and return to the more precise argument later.

A Step-by-Step Example

Use the following graph and start from A:

graph = {
    "A": [("B", 4), ("C", 1)],
    "B": [("D", 1)],
    "C": [("B", 2), ("D", 5)],
    "D": [],
}

Initially, A = 0 and every other distance is infinity. All vertices are unfinalized.

Step 1: Select A

A is selected because its tentative distance 0 is the smallest known value. Finalize A, then check its outgoing edges.

• B changes from infinity to 4 through A -> B.
• C changes from infinity to 1 through A -> C.
• D remains infinity because no route to it has been discovered.

State after the step:

Finalized: A=0
Tentative: B=4, C=1, D=infinity

Step 2: Select C

Among the unfinalized vertices, C is selected because 1 is smaller than B’s 4. Finalize C, then check its outgoing edges.

• The route A -> C -> B costs 1 + 2 = 3, so B changes from 4 to 3.
• The route A -> C -> D costs 1 + 5 = 6, so D changes from infinity to 6.
• The finalized distances of A and C remain unchanged.

State after the step:

Finalized: A=0, C=1
Tentative: B=3, D=6

Step 3: Select B

B is selected because its tentative distance 3 is smaller than D’s 6. Finalize B, then check its edge to D.

• The route A -> C -> B -> D costs 3 + 1 = 4, so D changes from 6 to 4.
• The finalized distances of A, C, and B remain unchanged.

State after the step:

Finalized: A=0, C=1, B=3
Tentative: D=4

Step 4: Select D

D is the only reachable unfinalized vertex, so its tentative distance 4 is the smallest. Finalize D. It has no outgoing edges, so no distance changes.

Finalized: A=0, C=1, B=3, D=4
Tentative: none

The final shortest-path distances are A=0, C=1, B=3, and D=4. The cheapest route from A to D is A -> C -> B -> D.

Relaxation

The updates in the example use a process called relaxation. Relaxation means updating the distance table when a route through the current vertex is cheaper than the best route known so far.

For an edge from current to neighbor, first calculate:

candidate = distance[current] + edge_weight

Then compare candidate with the neighbor’s current tentative distance:

if candidate < distance[neighbor]:
    update distance[neighbor]

If the candidate is smaller, it becomes the neighbor’s new tentative distance. Otherwise the existing value remains unchanged. Relaxation changes tentative values only. The algorithm does not reopen a finalized vertex under its required non-negative-edge assumption.

Why the Greedy Choice Is Safe

Selecting the current minimum is a greedy choice because the algorithm commits to the best option visible now. Non-negative edge weights are what make that commitment safe.

Intuition

Continuing along a path with non-negative edges cannot reduce the cost already accumulated. If a hidden route shorter than the current minimum existed, that route would have to pass through an earlier unfinalized vertex before reaching the selected vertex. The tentative distance to that earlier vertex would already be smaller than the selected distance, so it would have been selected first.

Because no such earlier vertex exists, a future continuation cannot reveal a cheaper route to the current minimum. Its tentative distance is therefore the true shortest-path distance and can be finalized.

A More Precise Argument

Suppose the algorithm selects vertex X, but there is a shorter hidden path from the start to X. Follow that path from the start and consider the first vertex Y on it that has not yet been finalized. The vertex immediately before Y on the path has already been finalized, so checking that predecessor’s outgoing edges should already have discovered a tentative distance to Y no greater than the cost of reaching Y along the hidden path.

All edges remaining from Y to X have non-negative weights. The cost of reaching Y must therefore be no greater than the total cost of the supposedly shorter path to X. That makes Y’s tentative distance smaller than X’s selected distance. But then Y, not X, should have been selected as the smallest unfinalized vertex. This contradicts how X was selected.

The contradiction shows that the shorter hidden path cannot exist. This argument explains the rule, but it is not necessary to repeat the proof every time the algorithm is used. On a first reading, the operating rule is the important part to retain.

Why Negative Edges Break the Argument

With a negative edge, continuing along a path can suddenly reduce its accumulated cost. Consider this graph:

A -> C costs 5
A -> X costs 10
X -> C costs -9

After checking A, the tentative distances are C=5 and X=10. The ordinary Dijkstra rule would select and finalize C first because 5 is the current minimum. However, continuing through X later produces the route A -> X -> C, whose total cost is 10 + (-9) = 1.

The earlier argument depended on the cost never decreasing as a path continues. The negative edge removes that guarantee, so the current minimum cannot be safely finalized by Dijkstra’s rule. Use an algorithm designed for negative weights, such as Bellman-Ford, when negative edges are possible.

Why Use a Priority Queue?

Conceptually, the algorithm repeatedly needs to find the unfinalized vertex with the smallest tentative distance. It could scan every unfinalized vertex each time, but repeated scans are expensive.

A priority queue is an implementation tool that retrieves the smallest stored distance efficiently. It does not supply Dijkstra’s correctness rule. Non-negative edge weights and the finalized-versus-tentative distinction supply that reasoning.

Python’s heapq does not provide a direct decrease-key operation for replacing an existing entry. When relaxation finds a lower distance, the implementation pushes a new (distance, vertex) tuple and leaves the older tuple in the heap. The older tuple becomes a stale entry.

Not every heap pop finalizes a vertex. If the popped distance differs from the current value in the distance table, the entry is stale and the implementation skips it. Only a popped entry that matches the current smallest recorded distance is processed as the up-to-date minimum.

Python Implementation

The implementation uses an adjacency list. Each key is a vertex, and its value is a list of (neighbor, weight) pairs. Every neighbor also appears as a key, even if it has no outgoing edges. The start must be a key, and every edge weight must be non-negative.

import heapq
 
 
def dijkstra(graph, start):
    distance = {node: float("inf") for node in graph}
    distance[start] = 0
 
    heap = [(0, start)]
 
    while heap:
        current_distance, node = heapq.heappop(heap)
 
        if current_distance != distance[node]:
            continue
 
        for neighbor, weight in graph[node]:
            candidate = current_distance + weight
 
            if candidate < distance[neighbor]:
                distance[neighbor] = candidate
                heapq.heappush(heap, (candidate, neighbor))
 
    return distance

Calling dijkstra(graph, "A") with the example graph returns:

{
    "A": 0,
    "B": 3,
    "C": 1,
    "D": 4,
}

The condition current_distance != distance[node] is the stale-entry check. For example, the heap can still contain (4, "B") after B improves to 3. When (4, "B") is eventually popped, the distance table already contains 3, so the code skips that entry. It does not finalize or process B again.

If a vertex cannot be reached from A, its distance remains float("inf"). Such a vertex is never placed in the heap and does not need to be finalized.

Reconstructing the Actual Path

The basic implementation returns only distances. To recover a path, store the parent that produced each improvement:

Function contract for the parent-tracking version:

• It accepts the same graph and start input contract as dijkstra.
• It returns (distance, parent).
• distance has the same meaning as before.
• parent[node] is the previous vertex on the best known path from start to node.
• parent[start] is None.
• Unreachable vertices do not appear in parent.

import heapq
 
 
def dijkstra_with_parent(graph, start):
    distance = {node: float("inf") for node in graph}
    parent = {start: None}
    distance[start] = 0
 
    heap = [(0, start)]
 
    while heap:
        current_distance, node = heapq.heappop(heap)
 
        if current_distance != distance[node]:
            continue
 
        for neighbor, weight in graph[node]:
            new_distance = current_distance + weight
 
            if new_distance < distance[neighbor]:
                distance[neighbor] = new_distance
                parent[neighbor] = node
                heapq.heappush(heap, (new_distance, neighbor))
 
    return distance, parent
 
 
def reconstruct_path(parent, target):
    if target not in parent:
        return None
 
    path = []
    current = target
 
    while current is not None:
        path.append(current)
        current = parent[current]
 
    return path[::-1]

With the example graph, reconstruct_path(parent, "D") returns ["A", "C", "B", "D"].

Complexity

With an adjacency list and a binary heap, each edge can cause a heap push when it improves a distance. Heap operations cost logarithmic time.

The usual complexity is O((V + E) log V) or O(E log V) for connected graphs, where V is the number of vertices and E is the number of edges.

The distance table uses O(V) space. The heap can hold multiple entries for the same vertex because of stale entries, so it can grow to O(E) entries in this common Python implementation.

When Dijkstra Is the Right Tool

Use Dijkstra when all of these are true:

• The problem asks for cheapest distance, cost, time, or risk from one start.
• Edges have weights.
• Every edge weight is non-negative.
• The graph may have cycles, so a simple topological order is not available.

If every edge has the same cost, breadth-first search is simpler. If negative weights are possible, Dijkstra is not reliable. If shortest paths are needed between every pair of vertices, an all-pairs algorithm may fit better.

Common Mistakes

Using Dijkstra with negative weights is the most important mistake. The algorithm’s correctness depends on non-negative edges.

Treating every heap pop as a finalization is also a mistake. In the heap-based Python version, compare the popped distance with the distance table and skip the entry when the values differ.

Another mistake is confusing shortest weighted path with fewest edges. Dijkstra minimizes total weight. It does not necessarily return the path with the smallest number of steps.

Finally, the graph representation must include all vertices that may appear as neighbors. If "D" appears in another vertex’s neighbor list, graph["D"] should exist, even if it is an empty list.

The Main Point

Dijkstra repeatedly finalizes the unfinalized vertex with the smallest tentative distance, then uses that vertex to look for cheaper routes to its neighbors. Non-negative weights make the finalization rule safe. A priority queue makes selecting the next vertex efficient, but the distance-table rule is the heart of the algorithm.