Dijkstra’s Algorithm Explained: Implementing with Python for Optimal Pathfinding

When a program needs the lowest-cost way between connected places, it has to compare possible routes. Dijkstra’s algorithm computes the cost of reaching each reachable point in a graph by adding the weights assigned to its edges.

In this piece, I’ll show how to implement Dijkstra’s algorithm in Python with heapq and reconstruct a route from predecessor links.

TL;DR: Dijkstra algorithm in Python

Dijkstra’s algorithm finds minimum path costs from one source in a graph whose edge weights are non-negative. The Python implementation below uses heapq and stores a predecessor for rebuilding the route.

• Represent each node by a dictionary of neighboring nodes and edge weights.
• Use a min-heap to select the next lowest tentative distance.
• Keep predecessor links if the result must include a path, not only its cost.
• Use another algorithm when any edge weight is negative.

What is Dijkstra’s algorithm?

Dijkstra’s algorithm computes shortest-path distances from one starting node to every reachable node in a weighted graph. A graph is a set of nodes connected by edges, and each edge’s weight is the cost of moving between its two endpoints.

For a road map, nodes can represent places and edge weights can represent distance or travel cost. The algorithm does not know what a weight means. It only adds the numbers, so the same method can minimize time, price, or another additive cost when each weight is non-negative.

It is a greedy algorithm because each iteration chooses the unprocessed node with the smallest tentative distance. Tentative means the best cost found so far, not yet proven final. With non-negative edges, once the smallest candidate is removed from the priority queue, no later route through another node can reduce it.

When the algorithm checks an edge from the current node to a neighbor, it compares the route through the current node with the neighbor’s saved distance. This comparison is called relaxation. If the new route costs less, the saved distance is replaced and the neighbor is queued for later processing.

The implementation uses an adjacency list: a dictionary maps each node to a dictionary of its neighbors and edge weights. In an undirected graph, include both directions for every connection. For a directed graph, include only the direction in which travel is allowed.

A node is a dictionary key with a neighbor dictionary of edge costs. The edge from A to C has weight 1 in the sample. A set of edge tuples can store the same facts, but each relaxation would need to search for the current node’s outgoing edges.

How to implement Dijkstra’s algorithm in Python

The implementation below accepts a graph, a source node, and an optional target. It returns all distances and predecessors when no target is supplied, or the target’s cost and route when one is supplied. The graph and program are in the same file so the full example runs with Python’s standard library.

Step 1: Initialize distances and predecessors

Set the source distance to zero because no edges are needed to reach it. Set all other distances to infinity, which marks them as undiscovered, and start the heap with the source candidate.

distances = {node: float("inf") for node in graph}
previous = {}
distances[source] = 0
queue = [(0, source)]

The distances dictionary is the algorithm’s working estimate. The previous dictionary records which node led to an improved estimate. It is separate from distances because a cost alone does not tell us which edges formed the route.

Step 2: Pop the cheapest candidate and relax its edges

heapq is Python’s built-in min-heap module. Each queue item is a pair of distance and node, so heappop returns the candidate with the lowest distance. When a better route to a node is discovered, push a new pair instead of searching through the heap to replace an old pair.

That lazy update strategy can leave old candidates in the heap. The check against distances[node] discards a candidate if a shorter route has already replaced it. It prevents stale work without requiring a decrease-key operation.

while queue:
    distance, node = heapq.heappop(queue)
    if distance != distances[node]:
        continue
    if target is not None and node == target:
        break
    for neighbor, weight in graph[node].items():
        if weight < 0:
            raise ValueError("Dijkstra requires non-negative edge weights")
        candidate = distance + weight
        if candidate < distances[neighbor]:
            distances[neighbor] = candidate
            previous[neighbor] = node
            heapq.heappush(queue, (candidate, neighbor))

Each edge is relaxed only when its start node is processed with the currently best distance. A successful relaxation updates both the numeric estimate and its predecessor, then adds the new candidate to the heap.

Step 3: Reconstruct the selected route

When a target is supplied, the loop can stop after that target is popped with its current best distance. Starting from the target, follow previous links backward until reaching the source, then reverse the collected nodes to put them in travel order.

if distances[target] == float("inf"):
    return None, []
path = [target]
while path[-1] != source:
    path.append(previous[path[-1]])
path.reverse()
return distances[target], path

If the target is still infinity, it was not reached and has no predecessor chain. Return a clear sentinel such as None and an empty list rather than attempting to index a missing predecessor. The complete function also checks that the source exists before starting.

Step 4: Run the complete example

Save the complete program as dijkstra_demo.py and run python3 dijkstra_demo.py. The graph includes two routes from A to E and a separate node Z, so the output shows a chosen route and an unreachable destination.

import heapq

def dijkstra(graph, source, target=None):
    if source not in graph:
        raise ValueError(f"unknown source: {source}")
    if target is not None and target not in graph:
        raise ValueError(f"unknown target: {target}")

    distances = {node: float("inf") for node in graph}
    previous = {}
    distances[source] = 0
    queue = [(0, source)]

    while queue:
        distance, node = heapq.heappop(queue)
        if distance != distances[node]:
            continue
        if target is not None and node == target:
            break
        for neighbor, weight in graph[node].items():
            if weight < 0:
                raise ValueError("Dijkstra requires non-negative edge weights")
            candidate = distance + weight
            if candidate < distances[neighbor]:
                distances[neighbor] = candidate
                previous[neighbor] = node
                heapq.heappush(queue, (candidate, neighbor))

    if target is None:
        return distances, previous
    if distances[target] == float("inf"):
        return None, []
    path = [target]
    while path[-1] != source:
        path.append(previous[path[-1]])
    return distances[target], list(reversed(path))

graph = {
    "A": {"B": 4, "C": 1},
    "B": {"A": 4, "C": 2, "D": 1},
    "C": {"A": 1, "B": 2, "D": 5},
    "D": {"B": 1, "C": 5, "E": 3},
    "E": {"D": 3},
    "Z": {},
}

print("From A:")
distances, _ = dijkstra(graph, "A")
for node, distance in distances.items():
    shown = "unreachable" if distance == float("inf") else str(int(distance))
    print(f"{node}: {shown}")

cost, path = dijkstra(graph, "A", "E")
print(f"A to E: {cost} via {' -> '.join(path)}")
print(f"A to Z: {dijkstra(graph, 'A', 'Z')}")

python3 dijkstra_demo.py

From A:
A: 0
B: 3
C: 1
D: 4
E: 7
Z: unreachable
A to E: 7 via A -> C -> B -> D -> E
A to Z: (None, [])

I ran python3 dijkstra_demo.py in this workspace. The route A to C to B to D to E costs 7, which is lower than the direct alternative through C to D to E, and Z remains unreachable. The image shows that same execution, including the AskPython terminal prompt.

Edge cases and complexity

Dijkstra’s algorithm depends on non-negative edge weights, and graph representation affects both correctness and performance. These constraints determine whether the result can be trusted and how much work the implementation performs.

Negative weights: reject them or choose an algorithm designed to handle them, such as Bellman-Ford. A negative edge can make a route cheaper after the algorithm has already finalized a node, invalidating its greedy assumption. The code checks weights while exploring edges.

Unreachable nodes: if there is no route from the source, the node’s distance stays infinity. In a target query, return a no-path result instead of reconstructing a route. For all-distances mode, callers can check math.isinf(distance).

Equal-cost routes: two distinct paths can have the same total weight. Since the code updates only when candidate is strictly less than the saved distance, it keeps one shortest route and does not collect every tied route. Which one it returns can depend on the order nodes are visited.

Source and target: the source must be a graph key. A target outside the graph is not reached by this implementation and should be validated at the API boundary if the function is used as a library. When source and target are the same, the cost is zero and the path contains that node alone.

The example function raises ValueError when the source or target is not a graph key. This distinguishes invalid input from a valid node that cannot be reached.

A zero-weight edge is valid because it cannot create a cheaper route by revisiting a node. Integer and floating-point weights both work when values can be added and compared consistently.

The graph must also be internally consistent: every neighbor named in an adjacency dictionary should be a node in the graph. Otherwise, distance initialization has no entry for that neighbor. Validate this when accepting user-provided graph data, or normalize all nodes before calling the algorithm.

Directed edges: store only allowed outgoing edges. An undirected connection needs entries in both adjacency dictionaries. Accidentally adding only one direction changes which routes are possible.

Use this checklist when adapting the code to another graph:

These checks separate a graph-data mistake from an algorithm mistake. If a route is missing, first verify that each intended direction is present. If the distance is unexpected, inspect the weights and confirm they measure the same additive quantity.

To return distances to every reachable vertex, call the function without a target and inspect its distances dictionary. For one destination, the target option avoids continuing once its shortest distance is final. If callers need every tied shortest route rather than one route, the predecessor structure must store multiple predecessors when candidate equals the existing distance.

With an adjacency list and a binary heap, the common complexity bound is O((V + E) log V) for a graph with V vertices and E edges, with lazy duplicate entries potentially affecting heap size. A simple implementation that scans every unvisited vertex for the minimum instead uses O(V squared) time. For sparse graphs, a heap avoids repeatedly scanning all vertices.

Dijkstra solves one-source paths. Floyd-Warshall can answer all-pairs questions, while A* can guide a search toward a goal when a useful distance estimate is available. Both require the graph costs to match the task.

Conclusion: keep distances and paths together

The key implementation choice is to store both the best-known cost and the predecessor that produced it. heapq selects the next candidate, relaxation improves estimates, and predecessor links turn the final distance into a route. Keep the non-negative weight condition visible wherever the function is used.

For another all-pairs approach, see Floyd-Warshall algorithm in Python. For goal-directed pathfinding, see A* algorithm in Python.