Dijkstra's shortest path

Grow a frontier of settled nodes, always expanding the cheapest one next — shortest paths when edges have weights.

Complexity: O((V + E) log V) time · O(V) space

The idea

Dijkstra generalizes BFS to weighted graphs. Instead of a plain queue it keeps a priority queue of tentative distances and always settles the closest unsettled node — at that moment, no cheaper route to it can exist (as long as no edge weight is negative).

Each settled node relaxes its neighbours: if going through it beats a neighbour's current tentative distance, the neighbour's distance and predecessor are updated.

Recovering the route

The distances alone don't name the path. Recording each node's predecessor at relaxation time lets you walk backwards from the target to the source and reverse the trail — the code's final loop does exactly that before painting it.

Watch for it on the canvas

Run it on the maze and watch the settled region creep outward from A in cost order until D is reached, then the recovered route lights up as the final path.

Try it on this graph:

# Dijkstra's shortest path, then highlight it. Uses edge weights via
# graph.getWeight(u, v) — unweighted edges count as 1.
import heapq

source, target = "A", "D"

dist = {node: float("inf") for node in graph.getNodes()}
prev = {node: None for node in graph.getNodes()}
dist[source] = 0
heap = [(0, source)]
seen = set()

while heap:
    d, node = heapq.heappop(heap)
    if node in seen:
        continue
    seen.add(node)
    for neighbour in graph.getNeighbors(node):
        if neighbour in seen:
            continue
        alt = d + graph.getWeight(node, neighbour)
        if alt < dist[neighbour]:
            dist[neighbour] = alt
            prev[neighbour] = node
            heapq.heappush(heap, (alt, neighbour))

print("distances:", dist)

if not graph.hasNode(target):
    print(f"no node {target!r} to trace a path to")
else:
    path = []
    node = target
    while node is not None:
        path.append(node)
        node = prev[node]
    path.reverse()
    print("path:", " -> ".join(path))
    graph.markPath(path)

Open this post in a project to thread the maze yourself.