Skip to content
G.

systems lab / 02

Routing Explorer

Trace the queue, tentative distances, and predecessor chain behind a shortest-path decision.

scenario 01 · simulated

Fewest links or lowest total weight?

BFS treats every link as equal. Dijkstra accounts for its weight. Play both traces, compare their routes, then edit a connection or take one offline and predict what changes.

Algorithm

Choose what “shortest” means

Breadth-first search uses a FIFO queue and minimizes the number of links. It deliberately ignores every weight printed on the graph.

invariant: visit hop layer k before layer k + 1

Graph experiment

Edit one connection

BFS ignores weights, but it still routes around a failed link.

Live graph

Source S to target T

weights 1–9 · one optional outage

Weighted routing graphSeven nodes connect source S to target T. Solid highlighted links show the finished route, the accent link is being considered, and a crossed dashed link is unavailable.21252415123SSourcefrontierANorthunseenBSouthunseenCUpper coreunseenDCoreunseenELower coreunseenTTargetunseen
  • Double ring = current node
  • Dashed ring = frontier
  • Crossed weight = failed link
  • Filled route = final answer

Step 1 / 28

bfs · initialize

Enqueue the source

BFS begins with the source in a first-in, first-out queue at hop distance 0.

Routing timeline playback

Playback

Algorithm state

Queue, distances, predecessors

FIFO frontier

  1. 1. S0 hops

Visit order

No node visited yet

Tentative distances and predecessors

NodeHopsPredecessorState
S0—frontier
A∞—unseen
B∞—unseen
C∞—unseen
D∞—unseen
E∞—unseen
T∞—unseen

Text trace

Every decision, in order

Select any row to inspect the exact graph and table snapshot for that decision.

Build notes

One graph, two definitions of shortest

The default graph is deliberately designed so BFS and Dijkstra can defend different answers. That disagreement is the lesson: an algorithm is only correct relative to the problem it was asked to solve.

  • Architecture

    Pure BFS and Dijkstra functions turn graph inputs into immutable snapshots. One reducer owns playback and graph experiments; SVG, the inspector, and the event log read the same active snapshot.

  • Tradeoff

    The teaching trace sorts a tiny array so queue changes stay inspectable. A production Dijkstra implementation would normally use a binary heap or another priority-queue structure.

  • Limitation

    The graph is undirected and accepts only positive integer weights from 1 to 9. It supports one failed link at a time and does not yet model directed edges, negative weights, or A* heuristics.

  • Performance

    Seven nodes keep every snapshot cheap enough to derive after an edit. The page and explanation remain Server Components while only the explorer boundary ships interactive React state.