Graph — weighted undirected (source = A)

Source (A)

Current node

Visited / finalized

Unvisited

Shortest path

Distance table — updated each step

Priority queue (unvisited nodes, sorted by distance)

Step 0 of 0

Press "Next step" to begin Dijkstra from node A.

Shortest paths from A

Python implementation

import heapq

def dijkstra(graph, start):
    # dist[v] = shortest known distance from start to v
    dist = {v: float('inf') for v in graph}
    dist[start] = 0
    prev = {v: None for v in graph}  # to reconstruct path

    # Min-heap: (distance, node)
    pq = [(0, start)]

    while pq:
        d, u = heapq.heappop(pq)    # pick node with smallest dist
        if d > dist[u]:
            continue              # stale entry, skip

        for v, weight in graph[u].items():
            new_dist = dist[u] + weight
            if new_dist < dist[v]:   # relaxation step
                dist[v] = new_dist
                prev[v] = u
                heapq.heappush(pq, (new_dist, v))

    return dist, prev

# Example graph
graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'A': 4, 'C': 1, 'D': 5},
    'C': {'A': 2, 'B': 1, 'D': 8, 'E': 10},
    'D': {'B': 5, 'C': 8, 'E': 2, 'F': 6},
    'E': {'C': 10, 'D': 2, 'F': 3},
    'F': {'D': 6, 'E': 3},
}
dist, prev = dijkstra(graph, 'A')

Interactive Dijkstra's shortest path algorithm — step through the algorithm and see distances update live on the graph