Dijkstra’s Algorithm in Python: heapq Shortest Paths

Dijkstra’s algorithm in Python finds the shortest distance from one start node to every other node in a weighted graph. It is a good fit when every edge weight is non-negative, such as road distances, network costs, or routing scores.

The most practical Python implementation uses an adjacency dictionary for the graph and heapq as a priority queue. The heap always gives us the currently known nearest unvisited node, which keeps the implementation fast and readable.

Graph representation

Use a dictionary where each key is a node and each value is another dictionary of neighbors and edge weights:

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

This structure is an adjacency list written with dictionaries. It is compact, easy to update, and works naturally with Python’s dictionary lookup.

Dijkstra’s algorithm code

from heapq import heappop, heappush
from math import inf


def dijkstra(graph, start):
    distances = {node: inf for node in graph}
    previous = {node: None for node in graph}
    distances[start] = 0
    heap = [(0, start)]

    while heap:
        current_distance, node = heappop(heap)

        if current_distance > distances[node]:
            continue

        for neighbor, weight in graph[node].items():
            if weight < 0:
                raise ValueError("Dijkstra's algorithm does not support negative weights")

            new_distance = current_distance + weight
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                previous[neighbor] = node
                heappush(heap, (new_distance, neighbor))

    return distances, previous

The distances dictionary stores the best known distance from the start node. The previous dictionary stores the parent node used to rebuild the shortest path later. The heap contains pairs of (distance, node).

Rebuild the shortest path

def shortest_path(previous, target):
    path = []
    node = target
    while node is not None:
        path.append(node)
        node = previous[node]
    return path[::-1]


distances, previous = dijkstra(graph, "A")
print(distances)
print(shortest_path(previous, "E"))

For the example graph, the shortest path from A to E is:

['A', 'C', 'B', 'D', 'E']

The total distance is 10: A -> C costs 2, C -> B costs 1, B -> D costs 5, and D -> E costs 2.

How the heapq priority queue helps

Without a priority queue, each step must scan all unvisited nodes to find the smallest distance. heapq avoids that full scan by keeping the smallest distance at the front of the heap. If an older heap entry is no longer the best distance, the current_distance > distances[node] check skips it.

With an adjacency list and binary heap, the usual time complexity is O((V + E) log V), where V is the number of vertices and E is the number of edges.

Directed, undirected, and unreachable nodes

The example graph is directed: an edge from "A" to "B" does not automatically create an edge from "B" back to "A". If your graph represents two-way roads, add both directions when building the adjacency dictionary:

graph["A"]["B"] = 4
graph["B"]["A"] = 4

For unreachable nodes, the distance stays as math.inf. Check that before showing a path to the user; otherwise a path-reconstruction helper may return only the target node, which can look like a valid path when it is not.

if distances["E"] == inf:
    print("No path found")
else:
    print(shortest_path(previous, "E"))

This check matters in real routing problems because disconnected components are common. A city map, dependency graph, or network topology may contain nodes that cannot be reached from the selected start node.

Common mistakes

• Using Dijkstra’s algorithm with negative edge weights. Use another algorithm when weights can be negative.
• Forgetting to initialize every node to math.inf.
• Returning only distances when the actual shortest path is also needed.
• Using a plain list as a queue, which makes the algorithm slower on larger graphs.
• Leaving out destination nodes that have no outgoing edges, such as "E": {} in the example.

Related Python guides

• Python heapq
• Min heap in Python
• Priority queue in Python
• Adjacency list in Python
• Nested dictionary in Python
• Breadth-first search in Python

Official references

• Python heapq documentation
• Python math.inf documentation
• Python tutorial: dictionaries

Conclusion

Dijkstra’s algorithm is easiest to implement in Python with an adjacency dictionary and heapq. Keep the graph weights non-negative, track both distances and previous nodes, and use the heap to process the next nearest node efficiently.