Dijkstra SPF Routing Workbench

Step through shortest-path-first selection, edge relaxation, predecessor updates, and OSPF route installation

Interactive Dijkstra shortest-path-first animation for learning link-state routing, tentative distances, edge relaxation, shortest path trees, OSPF metrics, ECMP, and failed-link behavior.

Animation Dijkstra OSPF SPF Link-State Routing

Dijkstra SPF Routing Workbench

Build the shortest path tree one decision at a time. Select the closest tentative router, relax its outgoing links, and watch OSPF-style next hops and total costs emerge from the topology.

A Root router

Init Current action

0/6 Final routers

0 SPT edges

Learning Brief

A link-state router knows the topology and link costs. Dijkstra SPF turns that map into a shortest path tree rooted at the local router.

Select Choose the unfinalized router with the lowest tentative distance.

Relax Check each neighbor to see whether the new path is cheaper.

Scenario

Controls

Root Router

Table View

Initialize Distances

Step 1

Set the root router cost to 0, all other routers to infinity, and leave every router tentative.

Topology and Shortest Path Tree

SPF Table

Diagnosis

Step Trace

Quick Reference

Distance Current best known total metric from the root router to a destination.

Predecessor The previous router on the current best path. Final predecessors form the shortest path tree.

Relaxation If cost(root to u) plus cost(u to v) is smaller than the current cost(root to v), update v.

Final Set Routers removed from the tentative set have their shortest path fixed, assuming non-negative link costs.

OSPF Output The SPF tree is converted into routing entries with destination, next hop, outgoing interface, and total cost.

ECMP Equal-cost paths can be retained as multiple next hops when the routing protocol and platform support it.

How to Read the Workbench

Topology Green edges belong to the current shortest path tree. Orange highlights the edge being tested.

SPF Table Final rows are fixed. Tentative rows may still improve when a later edge is relaxed.

Trace The trace records each select and relax decision so learners can audit why a route changed or stayed the same.

Technical Accuracy Notes

Non-Negative Costs Dijkstra SPF assumes link metrics are non-negative. Routing protocols such as OSPF use non-negative interface costs.

Topology First OSPF floods link-state advertisements so routers can build a synchronized link-state database before running SPF.

Area Scope Each router computes SPF for its area topology, then combines the result with inter-area and external route rules.

Failed Links When a link-state update removes or changes a link, routers rerun SPF against the updated database.

Next-Hop Derivation The predecessor tree gives the full path. Routing tables normally keep the next hop and outgoing interface, not every hop.

Complexity A simple implementation scans tentative routers; priority queues reduce work for larger topologies.

Source Links

OSPFv2 SPF RFC 2328 - OSPF Version 2

OSPFv3 RFC 5340 - OSPF for IPv6

OSPF Prefix/Link Attributes RFC 7684 - OSPFv2 Prefix/Link Attribute Advertisement