LeetCode Visualizer
How it worksAll visualizations

Step by step · Python

Dijkstra’s shortest path algorithm, visualized

Dijkstra’s algorithm finds the cheapest route from one vertex to every other in a graph whose edge weights are not negative. Its one idea: the closest vertex not yet settled can never get any closer.

How it works
Python
graph = {
    "A": {"B": 4, "C": 2},
    "B": {"A": 4, "D": 5},
    "C": {"A": 2, "D": 8, "E": 10},
    "D": {"B": 5, "C": 8, "E": 2},
    "E": {"C": 10, "D": 2},
}

start = "A"
dist = {name: 999 for name in graph}
dist[start] = 0
parent = {}
visited = set()

while len(visited) < len(graph):
    # Cheapest unvisited vertex.
    node = None
    for name in graph:
        if name not in visited:
            if node is None or dist[name] < dist[node]:
                node = name
    if node is None or dist[node] == 999:
        break
    visited.add(node)
    for neighbor in graph[node]:
        step = dist[node] + graph[node][neighbor]
        if step < dist[neighbor]:
            dist[neighbor] = step
            parent[neighbor] = node

print(dist)

How Dijkstra’s algorithm works

Every distance starts at infinity except the source, which is 0. Repeatedly pick the unvisited vertex with the smallest distance, mark it visited, and relax each of its edges: if going through it is cheaper than the neighbour’s current distance, update the distance and remember the parent. Stop when every reachable vertex has been visited.

The example graph has five vertices, and 999 stands in for infinity. From A, the route A → C → E costs 12 at first; it is beaten later by A → B → D → E, which costs 11.

What to watch for when it runs

  1. The distance table changes only when a cheaper route is found — watch E drop from 12 to 11.
  2. The vertex chosen each round is the cheapest unvisited one, not the one with the fewest edges.
  3. This version finds that vertex with a plain loop; production code uses a priority queue.

Time and space complexity

Time
O(V²) as written, O((V + E) log V) with a heap
Space
O(V)

The scan for the minimum is what makes this version quadratic. A binary heap makes each pick O(log V). Negative edge weights break the algorithm; Bellman-Ford handles them.

Related visualizations

Stuck on your own version?

Paste it into the visualizer and watch your own code run, line by line — bugs included.