---
title: "Dijkstra's Algorithm"
source: 'https://academia.sh/en/courses/algorithms/dijkstras-algorithm'
course: Algorithms
language: en
updated: '2026-08-17T18:07:37+00:00'
license: 'CC BY-SA 4.0'
---

# Dijkstra's Algorithm

Single-source shortest path on a weighted graph, the relaxation operation, the justification for the greedy choice, a priority-queue implementation, and the non-negative weight restriction.

The Data Structures course defined graphs and established breadth-first and depth-first
search. Breadth-first search found the shortest path in terms of **edge count**: every
edge was counted as equally costly.

In real problems, edges carry different costs — distance, time, fare. This topic builds
algorithms that work on weighted graphs, and its first question is the shortest path.

## Problem and Notation

**Single-source shortest path problem:** Given a weighted graph and a source vertex,
find the paths of lowest total weight from the source to every other vertex.

The same graph is used throughout this topic: vertices `A`–`F`, edges directed and
weighted.

```python
graph: dict[str, list[tuple[str, int]]] = {
    "A": [("B", 4), ("C", 2)],
    "B": [("C", 5), ("D", 10)],
    "C": [("E", 3)],
    "D": [("F", 11)],
    "E": [("D", 4)],
    "F": [],
}
```

The adjacency list representation suits sparse graphs, and traversing all edges is
$O(V + E)$. In dense graphs the adjacency matrix is preferred; the cost impact of this
choice was covered in the Data Structures course.

## Relaxation

The common building block of these algorithms is **relaxation**: lowering a known
estimate using a better path that has been found.

For each vertex, the best known distance from the source is kept as `u[v]`; initially
$0$ for the source and infinity for the rest. For an edge `(v, w)`:

$$
u[w] > u[v] + \text{weight}(v, w) \implies u[w] \leftarrow u[v] + \text{weight}(v, w)
$$

Relaxation never produces an incorrect value: `u[w]` is always the length of a **path
that actually exists**. Algorithms differ in the guarantee they give about when these
values become final.

## The Greedy Choice

Dijkstra's algorithm rests on this idea: **among vertices not yet settled, the one with
the smallest estimate is now settled.**

The justification rests on weights being non-negative. Any other path from the source
to `v` must pass through an unsettled vertex; since that vertex's estimate is not
smaller than `u[v]`, and the remaining edges cannot reduce the cost, the alternative
path cannot be shorter.

This reasoning gives the algorithm's invariant: **the distances of settled vertices are
the true shortest-path lengths.**

## Implementation

```python
import heapq


def dijkstra(graph: dict[str, list[tuple[str, int]]],
             source: str) -> tuple[dict[str, float], dict[str, str | None]]:
    """Returns (distances, previous vertices). Weights must not be negative."""
    distance: dict[str, float] = {vertex: float("inf") for vertex in graph}
    previous: dict[str, str | None] = {vertex: None for vertex in graph}
    distance[source] = 0
    queue: list[tuple[float, str]] = [(0, source)]
    settled: set[str] = set()

    while queue:
        dist, v = heapq.heappop(queue)
        if v in settled:               # stale entry: skip
            continue
        settled.add(v)
        for neighbor, weight in graph[v]:
            if dist + weight < distance[neighbor]:
                distance[neighbor] = dist + weight
                previous[neighbor] = v
                heapq.heappush(queue, (distance[neighbor], neighbor))
    return distance, previous


distance, previous = dijkstra(graph, "A")
print(distance)
# {'A': 0, 'B': 4, 'C': 2, 'D': 9, 'E': 5, 'F': 20}
```

The direct route from `A` to `D` via `A→B→D` has length 14; the algorithm finds the
`A→C→E→D` path with length 9. The greedy choice does not prevent a start that looks
longer from summing to less — because the choice looks at accumulated distances, not
at individual edges.

## Reconstructing the Path

Distance alone is not enough; which path was taken is also needed. The `previous`
dictionary carries this information: each vertex points to the vertex it was reached
from on the shortest path.

```python
def build_path(previous: dict[str, str | None], target: str) -> list[str]:
    path: list[str] = []
    vertex: str | None = target
    while vertex is not None:
        path.append(vertex)
        vertex = previous[vertex]
    return path[::-1]


print(build_path(previous, "F"))       # ['A', 'C', 'E', 'D', 'F']
print(build_path(previous, "B"))       # ['A', 'B']
```

These pointers form a **shortest path tree**: a tree rooted at the source that jointly
encodes the shortest paths to every vertex.

## Cost

Every vertex is settled at most once; every edge produces at most one relaxation and
one queue insertion. With a binary heap:

$$
O\big((V + E)\log V\big)
$$

The queue can hold multiple entries for the same vertex — the implementation here
skips stale entries as they are popped. This **lazy deletion** gives the same
asymptotic bound without requiring a priority queue with a decrease-key operation, and
it shortens the code noticeably.

In dense graphs ($E \approx V^2$), a variant that scans an array instead of using a
queue is $O(V^2)$ and can be faster. A theoretical variant using a Fibonacci heap gives
$O(E + V \log V)$; its constants are large, so it is rarely seen in practice.

## Common Variants

The basic structure adapts to different questions with small changes.

**Early exit for a single target.** If only the distance to a specific vertex is
needed, the search can stop the moment that vertex is popped from the queue; its value
is settled at that point. The remaining vertices are never processed.

**Multi-source search.** For questions like "distance to the nearest warehouse," all
sources are placed in the queue with zero distance at the start. This is equivalent to
a graph where a single artificial source draws a zero-weight edge to every warehouse;
it is the weighted counterpart of the multi-source breadth-first search from the Data
Structures course.

**Unreachable vertices.** The distance of a vertex unreachable from the source stays
infinite. Code that uses the result must test for this value; treating infinity as an
ordinary numeric distance leads to silent errors.

**Weights restricted to 0 and 1.** In this case a double-ended queue suffices instead
of a priority queue: a zero-weight edge is added to the front, a one-weight edge to the
back. The cost drops to $O(V + E)$ — the logarithmic factor is the price of weight
variety.

## The Non-Negative Weight Restriction

The algorithm's correctness rested on the assumption that "a settled vertex's value
can never drop again." A negative-weight edge breaks this assumption.

```python
with_negative_weight = {
    "A": [("B", 1), ("C", 2)],
    "B": [("D", 1)],
    "C": [("B", -2)],
    "D": [],
}

print(dijkstra(with_negative_weight, "A")[0])
# {'A': 0, 'B': 0, 'C': 2, 'D': 2}      — D wrong: the true distance is 1
```

Vertex `B` is settled via the direct edge of weight 1, and `D` is relaxed to 2 through
it. Then `C` is processed, and it turns out the `A→C→B` path is $2 + (-2) = 0$; `B`'s
value is corrected, but since `B` is already counted as settled, its outgoing edges are
never relaxed again. `D` stays at its old value.

The algorithm raises no error; **it silently produces the wrong result.** This is one
of the examples showing why documenting preconditions is not a formality.

An algorithm that works with negative weights is the subject of the next lesson.

## Summary

- The single-source shortest path problem asks for the lowest total-cost paths from the
  source to every vertex in a weighted graph.
- Relaxation lowers a vertex's estimated distance using a better path that has been
  found, and every estimate corresponds to a real path.
- Dijkstra's algorithm picks the smallest estimate among unsettled vertices; its
  correctness rests on weights being non-negative.
- The priority-queue implementation is $O((V + E)\log V)$; lazy deletion avoids needing
  a decrease-key operation.
- Previous-vertex pointers encode the shortest path tree and allow the path to be
  reconstructed.
- Under negative weight, the algorithm produces the wrong result without raising an
  error.

## Next Step

Negative weights arise in real problems: gain in currency conversion cycles, recovery
in a production plan. The next lesson builds the Bellman–Ford algorithm, which
abandons the greedy choice and relaxes every edge repeatedly, and shows why negative
cycles make the problem undefined.