Skip to content
← The Lab

Munich

The U-Bahn I actually live on: the full network, as a map you can plan a real journey on.

The one station on this map that is a real place. Munich is the city I actually live in, and its U-Bahn is the network I actually ride, so I built the whole thing: every line, every interchange, and a planner that finds you a real route across it.

The concept

A transit network is a graph: stations are nodes, track segments are edges, and a journey is a path. "Best route" is not one thing, though, the fewest stops and the fewest changes often disagree, and a sane planner weighs a transfer as costing more than a stop, because changing trains is the part humans hate. So the search runs over not just stations but station-and-line states, paying a penalty each time it switches lines.

The math

The planner is Dijkstra's algorithm over a state space of $(\text{station}, \text{line})$ pairs. Edge weights are one unit per stop, plus a transfer penalty $\tau$ whenever the line changes:

cost(path)=(stops)+τ⋅(interchanges)\text{cost}(\text{path}) = (\text{stops}) + \tau \cdot (\text{interchanges})

Dijkstra expands the cheapest frontier state first, so the first time it reaches the destination it has the optimal cost, no guessing. Tuning $\tau$ slides the answer between "fewest stops" ($\tau$ small) and "fewest changes" ($\tau$ large); the planner picks a $\tau$ that matches how a Münchner actually chooses.

Why it stays strange

The same algorithm routes your packets across the internet, your car across a map, and the slime mold's tubes across this very lab. A subway map feels like a designed object, but the good route through it is computed, and the computation is one of the oldest and most beautiful in the field. Garching to Marienplatz is a shortest-path problem, and the answer is a direct run on the U6.

Further reading

  • Dijkstra (1959), "A Note on Two Problems in Connexion with Graphs."
  • Münchner Verkehrs- und Tarifverbund (MVV), the real network this is built from.
@article{dijkstra1959,
  author  = {Dijkstra, Edsger W.},
  title   = {A Note on Two Problems in Connexion with Graphs},
  journal = {Numerische Mathematik},
  volume  = {1},
  pages   = {269--271},
  year    = {1959}
}