The internet is a graph of routers connected by links, and every packet that crosses it needs a decision at each hop: which neighbor gets it closer to the destination? Interior gateway protocols like OSPF solve this with link-state routing: every router floods its local link costs to the whole area, so every router ends up with an identical map of the topology, and each one independently runs Dijkstra's algorithm from itself to build a shortest-path tree to everywhere. Exterior gateway protocols like BGP instead run path-vector routing between autonomous systems: a router doesn't see the whole graph, only the paths its neighbors advertise, and it chooses between them by policy — attributes such as AS-path length or local preference — rather than by summing a pure numeric metric.
This simulation runs a genuine priority-queue Dijkstra over a live, editable graph of nine routers and eighteen weighted links — nothing here is a pre-drawn path. Pick a source and destination, edit link costs, and toggle between OSPF-style (cheapest total cost) and BGP-style (fewest hops, cost as tiebreaker) selection to see the two philosophies diverge on the same topology. Click a router or a link to fail it: the algorithm re-runs from scratch over the surviving topology, and the simulated convergence delay stands in for the real-world time a network spends flooding link-state advertisements and recomputing its shortest-path trees before traffic can flow again.
How does Dijkstra's algorithm actually find the shortest path?
Dijkstra's algorithm keeps a set of tentative distances from the source, initialized to infinity except the source itself (zero), and repeatedly pulls the unvisited node with the smallest tentative distance from a priority queue. It "relaxes" each of that node's edges — if going through it gives a shorter path to a neighbor, the neighbor's distance is updated. Once every reachable node has been visited, the tentative distances are optimal, and the shortest path to any destination can be read off by walking the predecessor pointers backward.
What is OSPF and how does it use Dijkstra?
OSPF (Open Shortest Path First) is a link-state interior gateway protocol used inside a single administrative network. Every router floods Link State Advertisements describing its directly connected links and their costs; once all routers agree on the same link-state database, each one independently runs Dijkstra's algorithm rooted at itself to compute the shortest path to every other router. Because every router uses the same input graph and the same deterministic algorithm, they all converge on consistent, loop-free routes.
How is BGP fundamentally different from OSPF?
BGP (Border Gateway Protocol) is a path-vector protocol that runs between autonomous systems — separate networks under different administrative control, such as different ISPs. A BGP router doesn't compute shortest paths over a shared topology; it only learns the specific paths its neighbors advertise and picks one using a policy decision process (local preference, AS-path length, origin, and other attributes) rather than pure cost minimization. This lets an ISP prefer a commercially favorable but longer route over a cheaper one, something a pure shortest-path algorithm can't express.
Why does routing convergence take time after a failure?
When a link or router fails, the routers adjacent to it must detect the failure, generate new link-state advertisements (or withdraw BGP routes), flood that information across the network, and every router must recompute its shortest-path tree before traffic can safely use the new routes. This detect-flood-recompute cycle is not instantaneous — OSPF convergence is typically sub-second to a few seconds, while BGP convergence across the global internet can take tens of seconds to minutes because updates propagate hop by hop between autonomous systems. Minimizing this gap is a genuine, ongoing area of network engineering research.
What happens to packets that are in flight when a link fails?
Packets already committed to a failed link are simply dropped — routing protocols have no way to recall a packet mid-flight. New packets entering the network during the convergence window may still be forwarded along stale routes until the updated shortest-path tree propagates, which can cause temporary loops or black holes. Only once every router's routing table reflects the new topology does traffic reliably follow the recomputed route.
Yes. If two adjacent routers update their routing tables at different times, one may briefly point toward the other believing it still has a valid path, creating a temporary loop until both converge on the same view of the topology. Link-state protocols like OSPF are comparatively loop-resistant because every router computes from an identical map, while distance-vector-style protocols are more prone to transient loops — a key reason link-state design became dominant inside large networks.
A link's cost (or metric) is a number representing how "expensive" it is to use — OSPF conventionally derives it from inverse bandwidth, while engineers can also weight it by latency, reliability, or monetary transit cost. Dijkstra doesn't care what the number represents, only that it's additive and non-negative; changing a link's cost changes which paths are cheapest without touching the physical topology, which is exactly how network operators steer traffic in production.
No single autonomous system can see the whole internet's topology, and no operator wants a foreign network unilaterally deciding its internal routes. Interior protocols like OSPF optimize routing inside a network the operator fully controls and trusts, using precise cost metrics. Exterior protocols like BGP glue tens of thousands of independent networks together using policy rather than trust, because AS operators need to enforce business relationships and cannot expose their internal topology to a global shortest-path computation.
Yes — OSPF and its cousin IS-IS both still run Dijkstra (or the closely related SPF algorithm) internally, and they remain the standard for interior routing in ISPs, data centers, and enterprise networks. Modern implementations use incremental SPF, which recomputes only the affected part of the shortest-path tree after a small topology change instead of rerunning the full algorithm, which is one of the main levers used to cut convergence time in large networks.