Dijkstra’s Shortest Path Algorithm

Dijkstra’s algorithm finds the shortest distance from a single starting vertex to every other vertex in a weighted graph, as long as no edge weight is negative. It is one of the most widely used graph algorithms in practice — it powers GPS route planning, network routing protocols, and countless “cheapest way to get from X to Y” problems in coding interviews. Understanding it well also unlocks related ideas like A* search and Prim’s algorithm for minimum spanning trees.

Overview: How Dijkstra’s Algorithm Works

Imagine four towns, A, B, C, and D, connected by roads with different driving times (in minutes): A-B takes 1, A-C takes 4, B-C takes 2, B-D takes 5, and C-D takes 1. Starting from town A, what is the fastest way to reach each other town? If every road took the same amount of time, a plain breadth-first search (BFS) would work: explore town-by-town, one “hop” at a time. But because roads take different amounts of time, the town you reach after the fewest hops is not necessarily the town you reach fastest. Dijkstra’s algorithm generalizes BFS to handle these weights by replacing BFS’s FIFO queue with a min-priority queue ordered by total travel time so far.

The algorithm keeps a running table of the best known (“tentative”) distance to every vertex, starting at 0 for the source and infinity for everywhere else. It repeatedly does the following: pull the not-yet-finalized vertex with the smallest tentative distance out of the priority queue, mark it finalized, and then relax every edge leaving it — that is, check whether going through this vertex offers a shorter path to each neighbor than what was previously known, and if so, update the neighbor’s tentative distance and push it back into the queue. This continues until the queue is empty.

Why the Greedy Choice Works

The reason Dijkstra’s algorithm is allowed to finalize a vertex’s distance the moment it is popped from the priority queue (and never revisit it) is that all edge weights are non-negative. When a vertex is popped, it has the smallest tentative distance of anything still in the queue. Any alternative, still-undiscovered path to it would have to pass through some other unfinalized vertex, whose distance is already known to be greater than or equal to the one just popped — and since edge weights can’t be negative, continuing from a farther vertex can only add more distance, never less. This guarantee breaks completely if a negative edge weight is allowed, which is exactly what the Common Mistakes section below demonstrates.

Dijkstra vs. Related Algorithms

Algorithm	Handles Negative Weights?	Typical Use Case
BFS	N/A (unweighted only)	Shortest path when every edge has equal weight
Dijkstra	No	Single-source shortest path, non-negative weights
Bellman-Ford	Yes (and detects negative cycles)	Shortest path when negative weights are possible
A* Search	No (needs an admissible heuristic)	Single-target shortest path with extra domain knowledge

Time and Space Complexity

With a graph represented as an adjacency list (a dict mapping each vertex to its neighbors and edge weights) and a binary heap (Python’s heapq) as the priority queue, every vertex is popped from the heap at most once as the “current” vertex, and every edge triggers at most one push to the heap (when it successfully relaxes a neighbor). A heap push or pop costs O(log V), where V is the number of vertices, because that’s the height of a binary heap holding up to O(E) entries. Summing the cost of up to V pops and E pushes gives O((V + E) log V) overall, where E is the number of edges.

Approach	Time Complexity	Space Complexity
Adjacency list + binary heap (heapq)	O((V + E) log V)	O(V + E)
Adjacency matrix + linear scan (no heap)	O(V^2)	O(V^2)
Adjacency list + Fibonacci heap (theoretical)	O(E + V log V)	O(V + E)

Python’s heapq has no built-in “decrease-key” operation, so instead of updating an entry in place, the implementations below push a brand-new (distance, vertex) tuple every time a shorter distance is found, and simply skip a popped entry if that vertex was already finalized (called lazy deletion). This can leave up to O(E) stale entries in the heap, but since log(E) is still O(log V) for any graph without parallel edges, the overall bound stays O((V + E) log V). Space is O(V + E) for the adjacency list, plus O(V) for the distances table, plus up to O(E) for heap entries.

Examples

The first example implements the four-town scenario from the Overview directly, printing the shortest travel time from A to every town.

import heapq


def dijkstra(graph: dict[str, dict[str, int]], start: str) -> dict[str, float]:
    distances: dict[str, float] = {node: float('inf') for node in graph}
    distances[start] = 0
    visited: set[str] = set()
    priority_queue: list[tuple[float, str]] = [(0, start)]

    while priority_queue:
        current_dist, current_node = heapq.heappop(priority_queue)
        if current_node in visited:
            continue
        visited.add(current_node)

        for neighbor, weight in graph[current_node].items():
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances


def main() -> None:
    graph = {
        'A': {'B': 1, 'C': 4},
        'B': {'A': 1, 'C': 2, 'D': 5},
        'C': {'A': 4, 'B': 2, 'D': 1},
        'D': {'B': 5, 'C': 1},
    }
    result = dijkstra(graph, 'A')
    for node in sorted(result):
        print(f"{node}: {result[node]}")


main()

Output:

A: 0
B: 1
C: 3
D: 4

Notice that the shortest way to C is not the direct road (which takes 4) but the detour through B (1 + 2 = 3) — the whole point of the algorithm is to find exactly this kind of non-obvious shortcut automatically.

The second example builds on the first by also tracking which vertex led to which (a predecessors table), so it can reconstruct the actual shortest path, not just its length. It also shows what happens for a vertex that is unreachable from the start — here, E has no edges connecting it to the rest of the graph.

import heapq
from typing import Optional


def dijkstra_with_path(
    graph: dict[str, dict[str, int]], start: str
) -> tuple[dict[str, float], dict[str, Optional[str]]]:
    distances: dict[str, float] = {node: float('inf') for node in graph}
    distances[start] = 0
    predecessors: dict[str, Optional[str]] = {node: None for node in graph}
    visited: set[str] = set()
    priority_queue: list[tuple[float, str]] = [(0, start)]

    while priority_queue:
        current_dist, current_node = heapq.heappop(priority_queue)
        if current_node in visited:
            continue
        visited.add(current_node)

        for neighbor, weight in graph[current_node].items():
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                predecessors[neighbor] = current_node
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances, predecessors


def reconstruct_path(
    predecessors: dict[str, Optional[str]], start: str, target: str
) -> Optional[list[str]]:
    path: list[str] = []
    node: Optional[str] = target
    while node is not None:
        path.append(node)
        node = predecessors[node]
    path.reverse()
    if path[0] != start:
        return None
    return path


def main() -> None:
    graph = {
        'A': {'B': 2, 'C': 5},
        'B': {'A': 2, 'D': 4},
        'C': {'A': 5, 'D': 1},
        'D': {'B': 4, 'C': 1},
        'E': {},
    }
    distances, predecessors = dijkstra_with_path(graph, 'A')
    print(f"Distances from A: {distances}")
    print(f"Shortest path A to D: {reconstruct_path(predecessors, 'A', 'D')}")
    print(f"Shortest path A to E: {reconstruct_path(predecessors, 'A', 'E')}")


main()

Output:

Distances from A: {'A': 0, 'B': 2, 'C': 5, 'D': 6, 'E': inf}
Shortest path A to D: ['A', 'B', 'D']
Shortest path A to E: None

reconstruct_path walks backward from the target through the predecessors table until it hits a vertex with no predecessor, then reverses the list. For E, that walk immediately hits None without ever reaching A, so the function correctly reports that no path exists rather than returning a bogus single-vertex “path”.

The third example applies the same function to a more realistic scenario: a small delivery network where edge weights are travel times in minutes between a warehouse and delivery hubs.

import heapq


def dijkstra(graph: dict[str, dict[str, int]], start: str) -> dict[str, float]:
    distances: dict[str, float] = {node: float('inf') for node in graph}
    distances[start] = 0
    visited: set[str] = set()
    priority_queue: list[tuple[float, str]] = [(0, start)]

    while priority_queue:
        current_dist, current_node = heapq.heappop(priority_queue)
        if current_node in visited:
            continue
        visited.add(current_node)

        for neighbor, weight in graph[current_node].items():
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances


def main() -> None:
    # Travel times in minutes between a warehouse and delivery hubs
    graph = {
        'Warehouse': {'Depot1': 4, 'Depot2': 1},
        'Depot1': {'Warehouse': 4, 'Depot2': 2, 'StoreA': 5},
        'Depot2': {'Warehouse': 1, 'Depot1': 2, 'StoreA': 8, 'StoreB': 10},
        'StoreA': {'Depot1': 5, 'Depot2': 8, 'StoreB': 2},
        'StoreB': {'Depot2': 10, 'StoreA': 2},
    }
    result = dijkstra(graph, 'Warehouse')
    for node in sorted(result):
        print(f"{node}: {result[node]}")


main()

Output:

Depot1: 3
Depot2: 1
StoreA: 8
StoreB: 10
Warehouse: 0

The direct road from the warehouse to Depot1 takes 4 minutes, but the algorithm finds a faster 3-minute route through Depot2 (1 + 2). This is the same shortcut-finding behavior as the first example, just with more realistic labels.

How It Works Step by Step

Tracing the first example (A, B, C, D) by hand shows exactly how the priority queue drives the algorithm:

1. Initialize: distances = {A: 0, B: inf, C: inf, D: inf}, queue = [(0, A)].
2. Pop (0, A). Relax A‘s edges: B becomes 1, C becomes 4. Queue: [(1, B), (4, C)].
3. Pop (1, B) (smallest). Relax B‘s edges: A is unchanged (2 is not less than 0), C improves from 4 to 3 (1 + 2), D becomes 6 (1 + 5). Queue: [(3, C), (4, C), (6, D)].
4. Pop (3, C). Relax C‘s edges: A and B don’t improve, D improves from 6 to 4 (3 + 1). Queue: [(4, C), (4, D), (6, D)].
5. Pop (4, C): this is a stale entry — C was already finalized at distance 3 — so it’s skipped.
6. Pop (4, D). Relax D‘s edges: no improvements. D is now finalized at 4.
7. Pop (6, D): stale, skipped. Queue is empty — done.

Final distances from A: B = 1, C = 3, D = 4, matching the printed output above. Notice how a vertex’s distance can be improved more than once before it is finally popped (C went from 4 to 3, and D went from 6 to 4) — this is exactly what the if distance < distances[neighbor] relaxation check is for.

Common Mistakes

Mistake 1: Using Dijkstra with negative edge weights

Dijkstra’s algorithm silently produces wrong answers when any edge weight is negative — it doesn’t raise an error, it just returns an incorrect distance. Here the same dijkstra function from Example 1 is run on a graph where C -> B has weight -10:

import heapq


def dijkstra(graph: dict[str, dict[str, int]], start: str) -> dict[str, float]:
    distances: dict[str, float] = {node: float('inf') for node in graph}
    distances[start] = 0
    visited: set[str] = set()
    priority_queue: list[tuple[float, str]] = [(0, start)]

    while priority_queue:
        current_dist, current_node = heapq.heappop(priority_queue)
        if current_node in visited:
            continue
        visited.add(current_node)

        for neighbor, weight in graph[current_node].items():
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances


def main() -> None:
    graph_with_negative_edge = {
        'A': {'B': 2, 'C': 5},
        'B': {'D': 1},
        'C': {'B': -10},
        'D': {},
    }
    result = dijkstra(graph_with_negative_edge, 'A')
    for node in sorted(result):
        print(f"{node}: {result[node]}")


main()

Output:

A: 0
B: -5
C: 5
D: 3

The true shortest distance to D is -4 (via A -> C -> B -> D = 5 + (-10) + 1), but the algorithm reports 3. Here’s why: B gets finalized early at distance 2 (via the direct edge), and only later does processing C reveal that B is actually reachable at -5. That correction does get written into distances[B], but because B was already marked visited, its outgoing edge to D is never re-relaxed with the better value, so D is stuck with the stale distance of 3. Once a vertex is finalized, Dijkstra never revisits it — and that assumption only holds when weights are non-negative. The fix is not a tweak to the code; it’s to use a different algorithm (Bellman-Ford) whenever negative weights are possible. A practical safeguard is to check for negative weights up front and fail loudly instead of returning a silently wrong answer:

import heapq


def has_negative_edge(graph: dict[str, dict[str, int]]) -> bool:
    return any(weight < 0 for neighbors in graph.values() for weight in neighbors.values())


def safe_dijkstra(graph: dict[str, dict[str, int]], start: str) -> dict[str, float]:
    if has_negative_edge(graph):
        raise ValueError("Dijkstra's algorithm requires non-negative edge weights")

    distances: dict[str, float] = {node: float('inf') for node in graph}
    distances[start] = 0
    visited: set[str] = set()
    priority_queue: list[tuple[float, str]] = [(0, start)]

    while priority_queue:
        current_dist, current_node = heapq.heappop(priority_queue)
        if current_node in visited:
            continue
        visited.add(current_node)

        for neighbor, weight in graph[current_node].items():
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances


def main() -> None:
    graph_with_negative_edge = {
        'A': {'B': 2, 'C': 5},
        'B': {'D': 1},
        'C': {'B': -10},
        'D': {},
    }
    try:
        safe_dijkstra(graph_with_negative_edge, 'A')
    except ValueError as error:
        print(f"Rejected: {error}")


main()

Output:

Rejected: Dijkstra's algorithm requires non-negative edge weights

Mistake 2: A mutable default argument in a recursive path helper

When writing a recursive helper that accumulates results — like building a path from a predecessors table — it’s tempting to use a list as a default argument:

def build_path(predecessors, node, path=[]):  # BUG: mutable default argument
    path.append(node)
    if predecessors[node] is None:
        path.reverse()
        return path
    return build_path(predecessors, predecessors[node], path)

This looks reasonable but is a classic Python trap: default argument values are created once, when the function is defined, not once per call. Every call that doesn’t explicitly pass path shares the exact same list object. Build a path for one target, and the next call (for a different target) starts with the leftover nodes from the first call still sitting in the list, silently corrupting the result. The fix is to default to None and create a fresh list inside the function body:

from typing import Optional


def build_path(
    predecessors: dict[str, Optional[str]], node: str, path: Optional[list[str]] = None
) -> list[str]:
    if path is None:
        path = []
    path.append(node)
    if predecessors[node] is None:
        path.reverse()
        return path
    return build_path(predecessors, predecessors[node], path)


def main() -> None:
    predecessors = {'A': None, 'B': 'A', 'C': 'A', 'D': 'B', 'E': None}
    print(build_path(predecessors, 'D'))
    print(build_path(predecessors, 'C'))


main()

Output:

['A', 'B', 'D']
['A', 'C']

Each top-level call now gets its own fresh list, so the second call’s result is unaffected by the first. This exact bug pattern shows up constantly in recursive backtracking and path-building code, so it’s worth checking for it any time you see a mutable literal ([] or {}) sitting in a function signature.

Best Practices

• Use an adjacency list (a dict of neighbor-weight maps) for typical sparse graphs; only reach for an adjacency matrix when the graph is dense or you need O(1) edge-weight lookups, since a matrix costs O(V^2) space regardless of how many edges actually exist.
• Never run plain Dijkstra on a graph that might contain negative edge weights — validate first, or switch to Bellman-Ford, which handles negative weights (and detects negative cycles) in O(V · E) time.
• Use heapq for the priority queue instead of repeatedly scanning a list for the minimum, which turns an O((V + E) log V) algorithm into an O(V^2) one.
• Since Python’s heapq has no decrease-key operation, use lazy deletion: push a new entry whenever a distance improves, and skip any popped entry for a vertex that’s already finalized.
• If you only need the distance to a single target (not to every vertex), you can stop as soon as that target is popped from the heap — it’s already finalized at that point.
• Use float('inf') as the “unknown distance” sentinel rather than an arbitrary large number, so comparisons stay correct no matter how large the real edge weights are.
• For unweighted graphs (or graphs where every edge has the same weight), use plain BFS instead — it’s simpler and already O(V + E) without needing a heap at all.

Practice Exercises

1. Extend the delivery-network example so it also prints the actual sequence of hubs (not just the total time) on the shortest route from Warehouse to StoreB. Hint: reuse the predecessors-tracking technique from the second example; the expected path is ['Warehouse', 'Depot2', 'Depot1', 'StoreA', 'StoreB'].
2. Write a few more test graphs for has_negative_edge and safe_dijkstra: one with all-positive weights (should run normally), one with a single negative weight (should raise ValueError), and one with a zero weight (should run normally, since zero is not negative).
3. Interview-style (based on LeetCode 743, “Network Delay Time”): given a list of directed edges times, where each edge is (source, target, weight), n nodes labeled 1 through n, and a starting node k, return the minimum time for a signal sent from k to reach every node, or -1 if some node can never be reached. Hint: this is exactly Dijkstra from k, followed by taking the maximum of all the finite distances found (and checking that every node got a finite distance at all).

Summary

• Dijkstra’s algorithm finds the shortest distance from one source vertex to every other reachable vertex, but only works correctly when every edge weight is non-negative.
• It works greedily with a min-priority queue: repeatedly finalize the closest not-yet-visited vertex, then relax (attempt to shorten) the tentative distances of its neighbors.
• Time complexity is O((V + E) log V) with an adjacency list and binary heap, or O(V^2) with an adjacency matrix and no heap (better for dense graphs); space complexity is O(V + E).
• Negative edge weights break the algorithm’s core assumption and can produce silently wrong answers — use Bellman-Ford instead when negative weights are possible.
• Python’s heapq has no decrease-key, so implementations push duplicate entries and use lazy deletion (skip a popped vertex that’s already finalized).
• Avoid mutable default arguments (path=[]) in recursive accumulator helpers like path reconstruction — default to None and initialize inside the function.
• For unweighted graphs, plain BFS is simpler and just as optimal — save Dijkstra for graphs where edge weights actually differ.