Dijkstra visualiser

What the visualiser is storing

Each successful relaxation changes two values: the cheapest distance found so far and the previous node on that route. The figure shows the distances; a real implementation also keeps the previous-node map so it can return a path, not just a cost.

In the worked graph, step to the end and read the distance beside each node. To reconstruct the route to a target, start there and follow previous nodes backwards until the source, then reverse that list.

Dijkstra in Python, including path reconstruction

This complete example uses an adjacency list and Python’s min-heap. It checks every edge before searching, so an early return cannot hide a negative weight. The arrival counter breaks equal-cost ties without comparing node labels; the distance check skips stale heap entries.

from heapq import heappop, heappush
from itertools import count
from math import inf, isfinite

def shortest_path(graph, source, target):
    graph = {node: list(edges) for node, edges in graph.items()}
    nodes = set(graph)
    for edges in graph.values():
        for neighbour, weight in edges:
            if not isfinite(weight) or weight < 0:
                raise ValueError("Dijkstra needs finite non-negative weights")
            nodes.add(neighbour)
    if source not in nodes or target not in nodes:
        raise ValueError("Source and target must be graph nodes")
    distance = {node: inf for node in nodes}
    previous = {}
    distance[source] = 0
    arrival = count()
    frontier = [(0, next(arrival), source)]

    while frontier:
        cost, _, node = heappop(frontier)
        if cost != distance[node]:
            continue  # A cheaper entry for this node won.
        if node == target:
            break

        for neighbour, weight in graph.get(node, []):
            candidate = cost + weight
            if candidate < distance[neighbour]:
                distance[neighbour] = candidate
                previous[neighbour] = node
                heappush(frontier, (candidate, next(arrival), neighbour))

    if distance[target] == inf:
        return inf, []

    path = []
    node = target
    while node != source:
        path.append(node)
        node = previous[node]
    path.append(source)
    return distance[target], list(reversed(path))

# Illustrative three-node graph: the cheaper route goes through C.
graph = {"A": [("B", 4), ("C", 2)], "C": [("B", 1)]}
print(shortest_path(graph, "A", "B"))
# (3, ['A', 'C', 'B'])

Use hashable node labels and finite non-negative numeric weights whose path sums remain finite. A node appearing only as an edge target has no outgoing edges. Unknown source or target nodes are rejected; an unreachable known target returns infinity and an empty path. This illustrative implementation is not a benchmark or a graph-library replacement.

Why the data structure changes the running time

The shortest-path rule stays the same. What changes is how much work it takes to choose the cheapest frontier node.

V counts vertices and E counts edges. The table assumes a simple graph. The lazy heap in the published code can hold O(E) entries, including stale ones: its general bound is O(V + E log(E + 1)) time, which gives the table’s bound for simple graphs. Distance and previous-node maps use O(V) space; the copied adjacency list and heap add O(V + E) space.

Choose the algorithm before the optimisation

Use breadth-first search when every edge has the same cost. Use Dijkstra when weights are non-negative. If a negative edge is possible, use an algorithm designed for it, such as Bellman–Ford; changing the priority queue cannot repair Dijkstra’s settled-node assumption.

The mechanism and complexity bounds were checked against the MIT 6.006 single-source shortest-path notes; the heap operations use Python’s heapq interface. The example and explanation here are original. MIT 6.006 lecture 16 · Python heapq documentation