A formal look at the problem model, the greedy strategy, correctness intuition, complexity bounds, and measured experimental behaviour of the simulator's implementation.
A road network is modelled as a weighted undirected graph G = (V, E, w). Junctions are vertices, roads are edges, and w(u, v) ≥ 0 is the travel cost of a road (distance, time, or fuel). The task is the single-source shortest-path problem: given a source s, compute the minimum total cost from s to every reachable vertex, and in particular to a chosen destination t.
The graph is stored as an adjacency list: a map from each vertex to the list of (neighbour, weight) pairs. Road networks are sparse — a junction rarely connects to more than a handful of roads — so this representation is far more economical than a matrix.
dist[v] ← ∞ for all v ∈ V
dist[s] ← 0
PQ ← min-heap containing (s, 0)
while PQ not empty:
(u, d) ← PQ.extractMin()
if u ∈ finalized: continue // stale entry
finalized ← finalized ∪ {u} // dist[u] is now provably optimal
if u = t: break // destination settled
for each (v, w) ∈ adj[u]:
if v ∉ finalized and dist[u] + w < dist[v]:
dist[v] ← dist[u] + w // relaxation
prev[v] ← u
PQ.insert(v, dist[v])
path ← reverse(t, prev[t], prev[prev[t]], …, s)The simulator executes exactly this procedure and records an event for every extraction, finalisation, edge examination and relaxation. The animation replays those recorded events — nothing about the visualisation is scripted or precomputed by hand.
Dijkstra is greedy: at every iteration it commits to the frontier vertex with the smallest tentative distance. This is safe precisely because weights are non-negative — any alternative route to that vertex must leave the settled set through a frontier vertex whose tentative distance is already at least as large, and appending non-negative edges can only increase the cost. Hence the extracted minimum can never be improved later, so it is finalized.
Finalising a vertex u is a statement about the source, not about a pair of adjacent nodes: it means the shortest distance from s to u is now settled. The edge prev[u] → u is therefore added to the shortest-path tree — that is the only moment an edge turns green in the simulator.
Relaxing (u, v) asks: does routing through u beat the best route to v found so far? If dist[u] + w(u, v) < dist[v], the tentative distance and predecessor are both overwritten. A vertex may be relaxed many times before it is settled — for example with A→C = 10, A→B = 4 and B→C = 3, vertex C is first given 10 via A, then improved to 7 via B. Because only the final predecessor edge is drawn when C is settled, the examined-but-rejected edge A→C is never highlighted.
The frontier is kept in a binary min-heap implemented from scratch (array-backed, sift-up on insert, sift-down on extract). Both operations cost O(log V). Rather than performing decrease-key, the implementation uses lazy deletion: an improved vertex is pushed again and stale entries are discarded on extraction. The heap then holds at most O(E) entries, which keeps the asymptotic bound unchanged while simplifying the data structure.
The predecessor array induces a shortest-path tree rooted at the source: every settled vertex contributes exactly one edge. The route to a particular destination is a single root-to-leaf path inside that tree, recovered by walking prev[t] → prev[prev[t]] → … → s and reversing. The simulator draws the tree in soft teal and the reconstructed destination route in a stronger teal, so the two are never confused.
With an adjacency list and a binary min-heap the bound is O((V + E) log V), where V = |vertices| and E = |edges|. It decomposes as:
Summing gives O(V log V + E log V) = O((V + E) log V). For sparse road networks where E = O(V), this is effectively O(V log V). A naive array-scan frontier instead gives O(V²), which only wins on extremely dense graphs; a Fibonacci heap improves the theoretical bound to O(E + V log V) but is slower in practice due to constant factors.
Total auxiliary space is O(V + E):
| Aspect | Adjacency list | Adjacency matrix |
|---|---|---|
| Space | O(V + E) | O(V²) |
| Iterate neighbours of u | O(deg(u)) | O(V) |
| Edge lookup (u, v) | O(deg(u)) | O(1) |
| Dijkstra total | O((V + E) log V) | O(V²) |
| Best for | Sparse road networks | Small dense graphs |
A city with 100,000 junctions and ~250,000 roads needs a matrix of 1010 cells, virtually all zero, while the adjacency list stores only the 250,000 real roads. Sparsity is why every practical routing engine uses list-style storage.
The benchmarks below run the same min-heap Dijkstra implementation in your browser on randomly generated connected graphs (weights 1–50), averaged over five trials. Nothing is hardcoded — press the button to measure on this machine.
With the edge factor held constant, E grows linearly with V, so the predicted curve is O(V log V) — slightly super-linear. Measured runtimes track that shape: doubling the vertex count a little more than doubles the time, rather than quadrupling it as an O(V²) implementation would. Counting-based metrics (edges examined, relaxations) are machine-independent and scale linearly with E, confirming that each edge is processed a constant number of times. Deviations at small sizes come from JIT warm-up, garbage collection and timer resolution; the density experiment isolates the E log V term by holding V fixed while increasing E.
Locations become vertices, roads become edges, and travel cost (time, distance, tolls or fuel) becomes the weight; the fastest route is then a shortest path. Dijkstra's Algorithm provides a fundamental model for understanding shortest-path route finding. Real navigation systems may use additional algorithms, heuristics, traffic data and optimizations — such as A* with geographic heuristics, bidirectional search, contraction hierarchies and live traffic re-weighting.
Dijkstra's Algorithm solves single-source shortest paths on non-negative weighted graphs by repeatedly finalising the closest unsettled vertex and relaxing its outgoing edges. Backed by an adjacency list and a binary min-heap it runs in O((V + E) log V) time and O(V + E) space, and the measured browser experiments agree with that prediction. The simulator makes the key idea visible: shortest distances are confirmed progressively from the source, and the route to a destination is only revealed once that destination itself is finalized.