Dijkstra's Algorithm Explained, Step by Step

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

What Is Dijkstra's Algorithm?

Dijkstra's algorithm, published by Edsger W. Dijkstra in 1959, finds the shortest path from a single source to every other node in a weighted graph. It works on both directed and undirected graphs, with one firm condition: every edge weight must be non-negative.

Think of the graph as a road network. Nodes are intersections, edges are roads, and each weight is the time or distance to travel that road. Dijkstra's algorithm answers the question every navigation app asks: what is the fastest route from where I am to everywhere else? It is one entry in the broader family covered in shortest path algorithms, and a fixture of the graph theory study roadmap.

The Core Idea

Dijkstra's algorithm is greedy. It keeps a tentative shortest distance to every node, and it repeats one simple move:

Always visit the unvisited node with the smallest known distance, then use it to improve its neighbours.

The insight that makes this correct: because all weights are non-negative, once you pick the closest unvisited node, no future path can ever reach it more cheaply. So the moment a node is chosen, its distance is final. That single guarantee is the whole algorithm.

Concretely, the algorithm maintains:

• A distance to every node, all starting at infinity except the source, which is 0.
• A priority queue (min-heap) that always hands back the closest unvisited node.
• A set of finalized nodes whose shortest distance is settled.

Improving a neighbour is called relaxation: if the path through the current node is shorter than the neighbour's recorded distance, you lower it.

How It Works, Step by Step

Let's run Dijkstra from node A on this weighted graph. The blue edges will form the final shortest-path tree, and the number beside each node is its final shortest distance from A.

Here is the trace. At each step we finalize the closest unvisited node (bold) and relax its neighbours. ∞ means "not reached yet".

Notice step three: visiting C lowered B from 4 to 3, because the route A → C → B (2 + 1) beats the direct edge A → B (4). That is relaxation doing its job. Watching this unfold on a live graph makes the pattern instant, which you can do in the algorithm visualizer.

Implementation in Python

The clean, interview-ready version uses Python's heapq as the priority queue. The graph is an adjacency list mapping each node to a list of (neighbour, weight) pairs.

import heapq

def dijkstra(graph, start):
    # Every node starts infinitely far away, except the source.
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # (distance so far, node)

    while pq:
        dist, node = heapq.heappop(pq)

        # A stale, longer entry for a node we already settled: skip it.
        if dist > distances[node]:
            continue

        for neighbour, weight in graph[node]:
            new_dist = dist + weight
            # Relaxation: found a cheaper way to reach the neighbour.
            if new_dist < distances[neighbour]:
                distances[neighbour] = new_dist
                heapq.heappush(pq, (new_dist, neighbour))

    return distances

Two details matter. First, we push a new entry instead of updating the heap in place, then skip stale entries with the dist > distances[node] check. This "lazy deletion" keeps the code simple and is standard practice. Second, the algorithm naturally computes distances to all nodes; to stop early at a single target, return as soon as you pop it.

Time and Space Complexity

The cost depends on the priority queue. Each edge can trigger at most one push, and each push or pop on a binary heap costs O(log V).

Space is O(V) for the distance table plus the queue. For the reasoning behind these bounds and how they compare across every graph algorithm, see the graph algorithms complexity guide and the one-page cheat sheet.

When Dijkstra Fails: Negative Weights

The greedy guarantee rests entirely on non-negative weights. Add a negative edge and the whole thing can break.

Suppose the algorithm finalizes a node because it looks closest, distance 5. Later it discovers a longer-looking route that passes through a -4 edge and actually reaches that node in 3. Too late: Dijkstra already declared 5 final and moved on. The answer is wrong.

Rule to remember: non-negative weights, use Dijkstra. Any negative weight, use Bellman-Ford, which relaxes every edge repeatedly and can also detect negative cycles.

Dijkstra vs Other Algorithms

Dijkstra is one tool among several. Picking the right one comes down to the graph.

The closest relative is A* search, which is Dijkstra plus a heuristic that steers the search toward a single goal. And Dijkstra itself is really breadth-first search upgraded from a plain queue to a priority queue.

Real-World Applications

• Navigation and maps: the shortest or fastest route between two places, the classic use.
• Network routing: link-state protocols such as OSPF use Dijkstra to compute forwarding tables.
• Games and robotics: movement costs across a map, often with A* built on top.
• Operations and logistics: least-cost paths in supply, telecom, and transit networks, a staple of operations research.