Introduction

You ask your phone for directions and the fastest route appears almost instantly. Then a crash blocks a highway, and before you reach it your route has already changed — rerouted around the jam in the blink of an eye. How does it keep up?

Finding the shortest path once is a solved, easy problem: Dijkstra's algorithm explores outward from your start, always extending the closest frontier, and lands the optimal route in polynomial time. For a small map, that's the whole story.

But a continent's road network has tens of millions of intersections, and traffic and closures change constantly. Re-running Dijkstra over the whole continent for every car, every few seconds, would melt the servers. The real challenge — dynamic shortest paths — is keeping answers fresh under nonstop change, fast enough to feel instant. That's where easy turns into a genuine frontier.

Reroute It

Try it. The map shows the shortest route from start to destination across a grid. Click a cell to close that road (or reopen it). The route instantly recomputes around the obstacle — and if you wall it off completely, it tells you there's no way through.

<p class="hint">The blue line is the <b>shortest route</b> from <span class="s">start</span> to
<span class="t">destination</span>. Click any cell to <b>close that road</b> (or reopen it) —
the route recomputes instantly around it.</p>
<div id="grid" class="grid"></div>
<div id="status" class="status"></div>
<button id="reset" type="button" class="ghost">Clear closures</button>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.hint .s { color: #0a7d33; font-weight: 700; } .hint .t { color: #c0392b; font-weight: 700; }
.grid { display: grid; gap: 2px; width: 100%; max-width: 360px; background: #e2e6eb; border: 2px solid #e2e6eb; border-radius: 8px; }
.cell { aspect-ratio: 1; background: #fff; cursor: pointer; display: flex; align-items: center; justify-content: center; font: 800 12px system-ui; transition: background .1s; }
.cell:hover { background: #eef3f7; }
.cell.wall { background: #44505c; cursor: pointer; }
.cell.path { background: #8fc7e8; }
.cell.start { background: #2a9d8f; color: #fff; }
.cell.end { background: #c0392b; color: #fff; }
.status { font-weight: 800; margin: .8rem 0 .6rem; min-height: 1.3em; }
button { font: 600 14px system-ui, sans-serif; padding: .5rem 1rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Dynamic shortest paths: a static shortest route (BFS here) recomputed on
    // every change. Static is easy; the hard, real-world part is doing this at
    // planet scale, thousands of times a second, under constant updates.
const N = 8;
const START = [0, 0], END = [N - 1, N - 1];
let wall = Array.from({ length: N }, () => new Array(N).fill(false));

function bfs() {
  const dist = Array.from({ length: N }, () => new Array(N).fill(-1));
  const prev = Array.from({ length: N }, () => new Array(N).fill(null));
  const q = [START]; dist[START[0]][START[1]] = 0;
  const D = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  while (q.length) {
    const [r, c] = q.shift();
    for (const [dr, dc] of D) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nc < 0 || nr >= N || nc >= N || wall[nr][nc] || dist[nr][nc] >= 0) continue;
      dist[nr][nc] = dist[r][c] + 1; prev[nr][nc] = [r, c]; q.push([nr, nc]);
    }
  }
  if (dist[END[0]][END[1]] < 0) return null;
  const path = new Set(); let cur = END;
  while (cur) { path.add(cur[0] + ',' + cur[1]); cur = prev[cur[0]][cur[1]]; }
  return { path, len: dist[END[0]][END[1]] };
}

function render() {
  const res = bfs();
  const g = document.getElementById('grid');
  g.style.gridTemplateColumns = 'repeat(' + N + ', 1fr)';
  let html = '';
  for (let r = 0; r < N; r++) for (let c = 0; c < N; c++) {
    let cls = 'cell';
    const isS = r === START[0] && c === START[1], isE = r === END[0] && c === END[1];
    if (wall[r][c]) cls += ' wall';
    else if (res && res.path.has(r + ',' + c) && !isS && !isE) cls += ' path';
    if (isS) cls += ' start'; if (isE) cls += ' end';
    html += '<div class="' + cls + '" data-r="' + r + '" data-c="' + c + '">' + (isS ? 'A' : isE ? 'B' : '') + '</div>';
  }
  g.innerHTML = html;
  g.querySelectorAll('.cell').forEach(el => el.addEventListener('click', () => {
    const r = +el.dataset.r, c = +el.dataset.c;
    if ((r === START[0] && c === START[1]) || (r === END[0] && c === END[1])) return;
    wall[r][c] = !wall[r][c]; render();
  }));
  const st = document.getElementById('status');
  if (res) { st.style.color = '#0a7d33'; st.textContent = fmt('✓ Route found — %len% steps.', { len: res.len }); }
  else { st.style.color = '#c0392b'; st.textContent = '✗ No route — the destination is walled off!'; }
}

document.getElementById('reset').addEventListener('click', () => { wall = Array.from({ length: N }, () => new Array(N).fill(false)); render(); });
render();
Result
Console

Every click is a tiny version of what your navigation app does at planetary scale, thousands of times a second. Here it's instant because the map is small; the magic of real systems is making it feel this instant on a map with millions of roads.

The Good News

This is a story of an easy problem pushed to astonishing speed:

  • Static is easy. Dijkstra (and A* with a heuristic) finds a shortest path in polynomial time — the textbook solved problem.
  • But re-solving is too slow at scale. A naive recompute on a continental graph for every query is far too expensive for live navigation.
  • Preprocess for blistering queries. Modern routing preprocesses the map once into clever structures — contraction hierarchies and hub labeling — so each route query then takes microseconds, even across a continent. This is one of algorithm engineering's great triumphs.
  • Updates are the frontier. When edge weights change (traffic) or edges vanish (closures), you'd like to update those structures rather than rebuild them. Fully dynamic shortest-path algorithms — maintaining answers under edge insertions and deletions — are an active research area, with deep recent progress.
  • In practice, layered tricks. Real systems combine fast queries, frequent partial rebuilds, traffic prediction and live updates to stay both correct and instant.

So routing sits happily in the easy zone for a single query, yet its dynamic version — keep everything optimal as the world shifts — is genuinely hard and still advancing.

Where It Matters

Keeping routes fresh under change runs much of how we move:

  • Live navigation: Google Maps, Waze and car GPS rerouting around traffic and closures in real time.
  • Ride-hailing and delivery: dispatching and routing fleets as conditions shift.
  • Logistics: continuously re-optimizing routes for trucks and couriers.
  • Video games: pathfinding for units as the map and obstacles change.
  • Network routing: data packets finding fast paths as links congest or fail.

Anywhere a "best route" must stay best while the underlying network keeps changing, dynamic shortest paths are doing the work.

Conclusion

Dynamic shortest paths are where an easy textbook problem meets the relentless pace of the real world. Finding one route is simple and solved; finding the right route for everyone, everywhere, while the map breathes with traffic and accidents, is a feat of algorithm engineering and ongoing research.

It's a fitting near-final stop on this tour: a reminder that "polynomial-time and solved" isn't always the end. Sometimes the next challenge isn't a harder problem but the same problem at a brutal scale and speed — and rising to that has given us the quiet miracle of a map that reroutes faster than you can notice the jam ahead.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/dynamic-shortest-paths/Content licensed under CC BY-NC 4.0.