Project — Dijkstra's Shortest-Path for Link-State Routing — Computer Networks

What it is#

A small implementation of the algorithm at the heart of OSPF, IS-IS, and every other link-state routing protocol. The input is a link-state database (LSDB): a global view of the network — every router, every link, every cost. The output is a per-source forwarding table: for every destination, “next hop is X, total cost is Y”. The algorithm is Dijkstra’s shortest-path with a binary heap, which runs in O((V + E) log V) and is what every OSPF router actually executes after a topology change.

The project teaches three things. First, the algorithm itself — the priority-queue version, not the textbook adjacency-matrix version with the O(V^2) outer loop. Second, the difference between cost (a scalar — the answer to “how far?”) and next hop (the routing decision — “send the packet to whom?”). Third, the fact that the LSDB is shared by every router but each router computes its own forwarding table — the algorithm runs N times across a network of N routers, with the same input, producing N different outputs.

When to use it#

Build this when you want to:

See Dijkstra in its routing-table form. Most algorithm courses show Dijkstra computing shortest distances. The interesting output for routing is next hop, which requires one extra bookkeeping field.
Compare against the distance-vector simulator. Same topology, same shortest paths, very different mechanics. The link-state version is one quiet local computation per router; distance-vector is a chatty multi-round exchange.
Understand what OSPF’s SPF runs after every LSA flood. When you see “OSPF SPF calculation took 12 ms” in a log, this is what was running.
Build a teaching toy. Print the priority queue at each step and you have a perfectly clear walkthrough of the algorithm.

Skip this and use networkx.shortest_path if you actually need shortest paths in production code — it’s tested, faster, and handles edge cases. The project is for understanding the algorithm and the routing-specific outputs.

How it works#

The link-state database#

In OSPF every router floods its link-state advertisement (LSA): “I’m router R, my neighbours are {N1: cost1, N2: cost2, ...}”. Routers store every LSA they hear. The result is a complete, identical map of the network on every router. We’ll skip the flooding (that’s a separate project) and start from the assembled LSDB.

LSDB = {
    'A': {'B': 4, 'C': 1},
    'B': {'A': 4, 'C': 2, 'D': 5},
    'C': {'A': 1, 'B': 2, 'D': 8, 'E': 10},
    'D': {'B': 5, 'C': 8, 'E': 2, 'F': 6},
    'E': {'C': 10, 'D': 2, 'F': 3},
    'F': {'D': 6, 'E': 3},
}

ASCII view:

        A ─── B
       1│  4 /│
        │   / │5
        C ── D
        │\   │\
        │ \  │ \
        │  \ │  \6
       10\  2│   \
          \  │    \
           E─┴─────F
              3

Costs are bidirectional and symmetric (which is what OSPF assumes for adjacency; asymmetric costs are fine for Dijkstra but unusual on a real LAN).

The algorithm#

"""dijkstra_routing.py — link-state shortest-path with forwarding tables.

For every source S we compute:
  - cost[D]      — total cost of the shortest path from S to D
  - next_hop[D]  — the first-hop neighbour to send the packet to
The forwarding table is the pair (cost, next_hop) for every destination D.
"""
import heapq
from dataclasses import dataclass


@dataclass(frozen=True)
class Route:
    cost: int
    next_hop: str | None  # None on the source itself


def dijkstra(lsdb: dict[str, dict[str, int]], source: str,
             verbose: bool = False) -> dict[str, Route]:
    """Single-source shortest paths from `source` over `lsdb`.

    Returns {destination: Route(cost, next_hop)}.
    Complexity: O((V + E) log V) with a binary heap.
    """
    if source not in lsdb:
        raise KeyError(f'source {source!r} not in LSDB')

    # cost[v] = best known cost from source to v
    cost: dict[str, int] = {source: 0}
    # parent[v] = predecessor on the best known path from source to v
    parent: dict[str, str | None] = {source: None}
    # settled[v] = True once we've extracted v from the heap (its cost is final)
    settled: set[str] = set()
    # heap entries are (tentative_cost, vertex). Stale entries are ignored on pop.
    heap: list[tuple[int, str]] = [(0, source)]

    step = 0
    while heap:
        d, u = heapq.heappop(heap)
        if u in settled:
            continue                       # stale entry; skip
        settled.add(u)
        step += 1
        if verbose:
            print(f'step {step:>2}: settle {u} at cost {d}')

        for v, weight in lsdb.get(u, {}).items():
            if v in settled:
                continue
            new_cost = d + weight
            if new_cost < cost.get(v, float('inf')):
                cost[v] = new_cost
                parent[v] = u
                heapq.heappush(heap, (new_cost, v))

    # Convert (cost, parent) into (cost, next_hop) by walking back to source.
    table: dict[str, Route] = {}
    for v in cost:
        if v == source:
            table[v] = Route(0, None)
            continue
        hop = v
        while parent[hop] is not None and parent[hop] != source:
            hop = parent[hop]
        # `hop` is now the neighbour of source on the path to v
        table[v] = Route(cost[v], hop)
    return table


def all_forwarding_tables(lsdb: dict[str, dict[str, int]]) -> dict[str, dict[str, Route]]:
    """Compute every router's forwarding table by running Dijkstra N times."""
    return {src: dijkstra(lsdb, src) for src in lsdb}


def print_table(source: str, table: dict[str, Route]) -> None:
    print(f'\nforwarding table at {source}:')
    print(f'  {"dest":<6} {"cost":<6} {"next-hop":<8}')
    for dest in sorted(table):
        r = table[dest]
        print(f'  {dest:<6} {r.cost:<6} {r.next_hop or "-":<8}')


if __name__ == '__main__':
    LSDB = {
        'A': {'B': 4, 'C': 1},
        'B': {'A': 4, 'C': 2, 'D': 5},
        'C': {'A': 1, 'B': 2, 'D': 8, 'E': 10},
        'D': {'B': 5, 'C': 8, 'E': 2, 'F': 6},
        'E': {'C': 10, 'D': 2, 'F': 3},
        'F': {'D': 6, 'E': 3},
    }
    print('Dijkstra walk from A:')
    table_a = dijkstra(LSDB, 'A', verbose=True)
    print_table('A', table_a)

    print('\nall forwarding tables:')
    for src, table in all_forwarding_tables(LSDB).items():
        print_table(src, table)

Sample output:

Dijkstra walk from A:
step  1: settle A at cost 0
step  2: settle C at cost 1
step  3: settle B at cost 3
step  4: settle D at cost 8
step  5: settle E at cost 10
step  6: settle F at cost 13

forwarding table at A:
  dest   cost   next-hop
  A      0      -
  B      3      C
  C      1      C
  D      8      C
  E      10     C
  F      13     C

Every destination from A goes via C — unsurprising, given A’s only cheap link is A-C at cost 1.

Walking through the algorithm#

Settling means “this vertex’s cost is final”. The heap holds tentative costs. The key invariant: when you pop (d, u) from the heap and u is not already settled, d is the true shortest cost to u. This is because:

All edge weights are non-negative.
Any path to u not yet considered must go through some unsettled vertex w with tentative cost >= d.
So that path has length >= d, and we can’t do better than d.

Per step:

Step 1: settle A at 0. Push (4, B) and (1, C). Heap: [(1, C), (4, B)].
Step 2: pop (1, C), settle C. C’s neighbours: B (currently 4) → via C is 1 + 2 = 3, better, update; D (currently inf) → 9; E (currently inf) → 11. Heap: [(3, B), (4, B-stale), (9, D), (11, E)].
Step 3: pop (3, B), settle B. B’s neighbours: A (settled), C (settled), D (currently 9) → via B is 3 + 5 = 8, better, update. Heap: [(4, B-stale), (8, D), (9, D-stale), (11, E)].
Step 4: pop (4, B-stale) — B is settled, skip. Pop (8, D), settle D. Update E to 8 + 2 = 10 (was 11) and F to 8 + 6 = 14.
Step 5: settle E at 10. E’s neighbour F → 10 + 3 = 13, better than 14. Update.
Step 6: settle F at 13.

From parent to next hop#

The parent dict stores “who came right before me on the best path”. To get the next hop, walk backward from the destination toward the source until you find a vertex whose parent is the source — that vertex is the source’s neighbour on the path. This is what the loop at the bottom of dijkstra() does.

Some implementations store next_hop directly during relaxation:

# alternative: track next_hop during relaxation
if new_cost < cost.get(v, float('inf')):
    cost[v] = new_cost
    next_hop[v] = u if u == source else next_hop[u]
    heapq.heappush(heap, (new_cost, v))

That’s O(1) per relaxation and avoids the post-walk. Either form is correct; the parent-then-walk version is slightly easier to debug because parents are recognisable in the output.

Variants#

All-pairs. Run Dijkstra from every source (all_forwarding_tables above). For a network of N routers and average degree d, this is O(N * (N + Nd) log N) = O(N^2 d log N). Fine for a few thousand routers; the Floyd-Warshall O(N^3) form is sometimes simpler if d is large.
Equal-cost multi-path (ECMP). Track all equally-good predecessors, not just one. The forwarding table then maps dest -> list[next_hop], and the router picks one per flow (typically by hashing the 5-tuple).
Fibonacci heap. Improves the theoretical bound to O(E + V log V). In practice the binary heap is faster for typical OSPF area sizes (a few hundred routers).
A* for an LSDB with coordinates. If routers have positions and you have a usable heuristic, A* dominates pure Dijkstra. Not how OSPF does it, but a useful experiment.
Incremental SPF. Real OSPF doesn’t re-run SPF from scratch on every LSA. It runs the full thing initially, then computes incremental changes when one LSA arrives. The incremental versions are non-trivial; the from-scratch version is what every implementation falls back to in the worst case.
Bellman-Ford variant. Same shortest paths, no priority queue, O(VE). Useful as a sanity check when you don’t trust the heap implementation. Also: handles negative edge weights, which Dijkstra cannot.

Trade-offs#

Link-state + Dijkstra — every router has the full topology and computes its own forwarding table locally. No count-to-infinity, fast convergence (one flood + one SPF run), and the algorithm is well-understood. But every router stores O(N + E) state and every topology change floods the network.

Distance-vector — every router stores only its own table (O(N) memory) and only exchanges with neighbours. Cheaper memory and bandwidth in steady state, but the protocol is chatty around topology changes and has fundamental loop problems that need bandaids (split-horizon, hold-down, infinity).

Other tensions worth weighing:

Heap size. Pushing on every relaxation means up to E entries in the heap. That’s the price of avoiding decrease-key. For sparse graphs this is fine; for dense graphs the adjacency-matrix O(V^2) Dijkstra is sometimes faster.
int vs float cost. OSPF cost is an integer (1–65535). Use int to make ECMP equality exact; float introduces floating-point near-misses.
Eager vs lazy stale-handling. “Eager” decrease-key keeps the heap small but needs a heap with index lookup. “Lazy” (push on every relaxation, skip on pop) keeps the heap simple but bigger. The lazy version above is what most implementations use.

Why doesn't Dijkstra work with negative edge weights?

The correctness argument depends on “any path through an unsettled vertex is at least as long as the popped cost”. With negative weights, an as-yet-unsettled vertex could be reached via a path that drops total cost below d. The classical counterexample: A -1-> B, A -3-> C, C -5-> B. Dijkstra settles B at cost 1 from A directly, then can’t improve it; but the true cost via C is 3 + (-5) = -2. Bellman-Ford or SPFA handle this.

Common pitfalls#

Recomputing next_hop by re-running Dijkstra in reverse. The walk-back works once the parent map is built; there’s no need for a second Dijkstra. Easy mistake to make if you’re tired.
Skipping the if u in settled: continue check. Without it, the same vertex gets processed multiple times and the complexity degrades to O(E^2) for pathological inputs. The guard is one line and is mandatory.
Mutating the LSDB during the run. Dijkstra assumes a static graph. If your simulator updates the LSDB from an LSA-flooding thread, snapshot the dict first or run inside a lock.
Using dict[str, float] and getting inf propagation. Comparing float('inf') + 1 works in Python but produces inf; harmless but misleading in print output. Prefer int with a sentinel like INFINITY = sys.maxsize.
Returning costs only. A routing table needs next_hop. Drop it and you have a distance table, not a forwarding table.
Treating asymmetric link costs as symmetric. Real LSDBs may have A->B = 1 and B->A = 5 (e.g. interface speeds differ). Don’t fold the LSDB into an undirected graph unless your protocol guarantees symmetry.
Forgetting the u == source case. If a destination’s parent is the source, the next hop is the destination itself (a direct neighbour). The walk-back loop must handle this.
Running Dijkstra once and reusing the result on every router. Each source needs its own run. The LSDB is shared; the forwarding table is per-router.
Not handling disconnected components. A vertex with no path from the source never appears in cost. Iterating for v in lsdb instead of for v in cost will throw KeyError.
Optimising before measuring. A Python heap-based Dijkstra over 500 routers and 2000 links takes well under a millisecond. Beware spending hours on a heap micro-optimisation when the algorithm is already fast.