Dijkstra’s Algorithm in Python: Shortest Paths With heapq

Quick answer: Dijkstra’s algorithm finds shortest paths from one source in a graph with non-negative edge weights. In Python, store adjacency lists, keep tentative distances in a heapq priority queue, relax edges, and skip stale heap entries when a node’s distance has already improved.

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). Dijkstra’s algorithm is A* with no heuristic estimate; A* Algorithm in Python for Pathfinding shows how an admissible heuristic changes the queue priority.

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.

State The Graph Contract

Represent each node’s outgoing neighbors and weights consistently, define the source, and decide how unreachable nodes are reported. Dijkstra’s correctness depends on every edge weight being at least zero.

Relax Edges

For a current node u and edge to v with weight w, calculate candidate = distance[u] + w. If candidate improves distance[v], update it and push the new pair into the heap.

Handle Stale Heap Entries

heapq does not support decrease-key directly. Push improved pairs and, when one is popped, ignore it if its distance is greater than the current best-known value for that node.

Recover A Shortest Path

Store a predecessor when a distance improves. Once the destination is reached, walk predecessors backward and reverse the collected nodes, while handling the unreachable case explicitly.

Know When Dijkstra Is Wrong

Negative edges invalidate its greedy assumption. Use an algorithm suited to negative weights, and use breadth-first search for unweighted graphs where every edge has equal cost.

Measure Complexity And Test

With a binary heap and adjacency list, the usual bound is O((V + E) log V). Test cycles, ties, disconnected nodes, a source equal to the target, and a graph that includes a rejected negative edge.

The official heapq documentation covers the priority queue primitive. Related Python Pool references include debug logging and algorithm tests.

For related graph workflows, compare priority queues, algorithm tests, and trace logging when validating shortest paths.

Frequently Asked Questions

When should I use Dijkstra’s algorithm?

Use it for shortest paths from one source when edge weights are non-negative and you need distances to some or all reachable nodes.

Why use heapq in a Python implementation?

heapq efficiently retrieves the next smallest tentative distance, reducing repeated scans of all unvisited vertices.

Can Dijkstra handle negative edge weights?

No. Negative weights can invalidate the greedy choice; use an algorithm such as Bellman-Ford when negative edges are required.

Why can the heap contain duplicate nodes?

A later relaxation can improve a node before its old heap entry is removed, so skip stale entries whose distance no longer matches the best-known value.