Dijkstra

Problem

Given a weighted directed graph and a source vertex, find the shortest path from the source to every other reachable vertex.

Approach

Dijkstra's algorithm using a min-heap (priority queue). Greedily expand the nearest unvisited node and relax its outgoing edges.

Algorithm Flow

flowchart TD
    A["Initialize dist[source] = 0<br/>dist[all others] = inf"] --> B["Push (0, source)<br/>to min-heap"]
    B --> C{"Heap empty?"}
    C -- Yes --> D["Return dist array"]
    C -- No --> E["Pop (d, u) with<br/>smallest distance"]
    E --> F{"d > dist[u]?<br/>(stale entry)"}
    F -- Yes --> C
    F -- No --> G["For each neighbor v<br/>of u with weight w"]
    G --> H{"d + w < dist[v]?"}
    H -- Yes --> I["dist[v] = d + w<br/>Push (d+w, v) to heap"]
    H -- No --> J["Skip — no improvement"]
    I --> G
    J --> G
    G -- "All neighbors<br/>processed" --> C

    style A fill:#7c3aed,color:#fff
    style D fill:#059669,color:#fff
    style F fill:#f59e0b,color:#000

When to Use

Shortest path with NON-NEGATIVE weights. Flight routing, network latency, road navigation. For negative weights use Bellman-Ford instead. ASI relevance: core of route optimization in PRESCIENCE.

Complexity

Time	O((V + E) log V)
Space	O(V + E)

Implementation

SolutionTestsChallenge

dijkstra

Single-source shortest paths with non-negative edge weights.

Problem

Given a weighted directed graph and a source vertex, find the shortest path from the source to every other reachable vertex.

Approach

Dijkstra's algorithm using a min-heap (priority queue). Greedily expand the nearest unvisited node and relax its outgoing edges.

When to use

Shortest path with NON-NEGATIVE weights. Flight routing, network latency, road navigation. For negative weights use Bellman-Ford instead. ASI relevance: core of route optimization in PRESCIENCE.

Complexity

Time: O((V + E) log V) Space: O(V + E)

dijkstra

dijkstra(
    num_nodes: int,
    edges: Sequence[tuple[int, int, float]],
    source: int,
) -> list[float]

Return shortest distances from source to all nodes.

edges is a list of (u, v, weight) with weight >= 0. Unreachable nodes have distance float('inf').

dijkstra(4, [(0, 1, 1), (0, 2, 4), (1, 2, 2), (1, 3, 6), (2, 3, 3)], 0) [0, 1, 3, 6]

Source code in src/algo/graphs/dijkstra.py

def dijkstra(
    num_nodes: int,
    edges: Sequence[tuple[int, int, float]],
    source: int,
) -> list[float]:
    """Return shortest distances from *source* to all nodes.

    *edges* is a list of (u, v, weight) with weight >= 0.
    Unreachable nodes have distance ``float('inf')``.

    >>> dijkstra(4, [(0, 1, 1), (0, 2, 4), (1, 2, 2), (1, 3, 6), (2, 3, 3)], 0)
    [0, 1, 3, 6]
    """
    adj: list[list[tuple[int, float]]] = [[] for _ in range(num_nodes)]
    for u, v, w in edges:
        adj[u].append((v, w))

    dist: list[float] = [INF] * num_nodes
    dist[source] = 0
    heap: list[tuple[float, int]] = [(0, source)]

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))

    return dist

tests/graphs/test_dijkstra.py

"""Tests for Dijkstra's shortest-path algorithm."""

from algo.graphs.dijkstra import INF, dijkstra


class TestDijkstra:
    def test_simple_path(self) -> None:
        edges = [(0, 1, 1), (1, 2, 2), (0, 2, 4)]
        assert dijkstra(3, edges, 0) == [0, 1, 3]

    def test_diamond_graph(self) -> None:
        edges = [(0, 1, 1), (0, 2, 4), (1, 2, 2), (1, 3, 6), (2, 3, 3)]
        assert dijkstra(4, edges, 0) == [0, 1, 3, 6]

    def test_unreachable_node(self) -> None:
        edges = [(0, 1, 5)]
        dist = dijkstra(3, edges, 0)
        assert dist[0] == 0
        assert dist[1] == 5
        assert dist[2] == INF

    def test_single_node(self) -> None:
        assert dijkstra(1, [], 0) == [0]

    def test_parallel_edges(self) -> None:
        edges = [(0, 1, 10), (0, 1, 3)]
        assert dijkstra(2, edges, 0) == [0, 3]

    def test_longer_graph(self) -> None:
        edges = [
            (0, 1, 7),
            (0, 2, 9),
            (0, 5, 14),
            (1, 2, 10),
            (1, 3, 15),
            (2, 3, 11),
            (2, 5, 2),
            (3, 4, 6),
            (4, 5, 9),
        ]
        dist = dijkstra(6, edges, 0)
        assert dist == [0, 7, 9, 20, 26, 11]

Implement it yourself

Run: just challenge graphs dijkstra

Then implement the functions to make all tests pass. Use just study graphs for watch mode.

Reveal Solution

dijkstra

Single-source shortest paths with non-negative edge weights.

Problem

Given a weighted directed graph and a source vertex, find the shortest path from the source to every other reachable vertex.

Approach

Dijkstra's algorithm using a min-heap (priority queue). Greedily expand the nearest unvisited node and relax its outgoing edges.

When to use

Shortest path with NON-NEGATIVE weights. Flight routing, network latency, road navigation. For negative weights use Bellman-Ford instead. ASI relevance: core of route optimization in PRESCIENCE.

Complexity

Time: O((V + E) log V) Space: O(V + E)

dijkstra

dijkstra(
    num_nodes: int,
    edges: Sequence[tuple[int, int, float]],
    source: int,
) -> list[float]

Return shortest distances from source to all nodes.

edges is a list of (u, v, weight) with weight >= 0. Unreachable nodes have distance float('inf').

dijkstra(4, [(0, 1, 1), (0, 2, 4), (1, 2, 2), (1, 3, 6), (2, 3, 3)], 0) [0, 1, 3, 6]

Source code in src/algo/graphs/dijkstra.py

def dijkstra(
    num_nodes: int,
    edges: Sequence[tuple[int, int, float]],
    source: int,
) -> list[float]:
    """Return shortest distances from *source* to all nodes.

    *edges* is a list of (u, v, weight) with weight >= 0.
    Unreachable nodes have distance ``float('inf')``.

    >>> dijkstra(4, [(0, 1, 1), (0, 2, 4), (1, 2, 2), (1, 3, 6), (2, 3, 3)], 0)
    [0, 1, 3, 6]
    """
    adj: list[list[tuple[int, float]]] = [[] for _ in range(num_nodes)]
    for u, v, w in edges:
        adj[u].append((v, w))

    dist: list[float] = [INF] * num_nodes
    dist[source] = 0
    heap: list[tuple[float, int]] = [(0, source)]

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))

    return dist