Skip to content

0002. Link-labelled shortest paths and an explicit turn table

Decision. The shortest-path search labels links, not nodes, and works from an explicit turn table stored in CSR form indexed by incoming link.

Why. With bans or penalties, the best way into a node depends on the way out. A node-labelled Dijkstra is wrong in that case. Labelling links makes turn costs and bans exact without building an expanded graph.

Turn table. Built from the network: every pair (e, f) where f leaves the node e enters, minus U-turns (unless allowed), turns at endpoint nodes, and banned turns. Exceptions are validated and an exception that names a turn that does not exist is an error, which catches typos in user files. A path is stored as its links and turn ids, so turn flows follow directly.

Costs are separate arrays. turn_costs[turn id] is a slice passed to the search, so fixed penalties and flow-dependent delays use the same code.

Validation. The banned-turn example, free turns against node-based Dijkstra on Sioux Falls, and non-zero turn costs against a naive relaxation.