Routing — the shortest path through a network

Routing problems are a settled category — and one of the most common places engineering teams waste weeks reinventing the standard answer.

1. 01
   Build the road graph as a DiGraph with travel-minute edge weights, then call dijkstra once. The return is a HashMap from each reachable intersection to the cheapest distance. Sixty years of algorithms, four lines of glue.

   use petgraph::algo::dijkstra;
   use petgraph::graph::{DiGraph, NodeIndex};
   
   fn fastest_routes(road: &DiGraph<&str, u32>, from: NodeIndex)
       -> std::collections::HashMap<NodeIndex, u32>
   {
       dijkstra(road, from, None, |e| *e.weight())
   }

2. 02
   |e| *e.weight() is a closure — Rust's name for an anonymous function. Other languages call this a lambda. The pipes | | wrap the parameter list; everything after is the body. Here the closure takes one parameter e (a reference to an edge), calls e.weight() to get &u32 (a reference to the weight stored inside the graph), then uses the prefix * — the dereference operator — to read the underlying u32 out of that reference. The closure tells Dijkstra how to extract a cost from each edge; swap it for a different closure and the algorithm uses a different cost.

   // |e| *e.weight()
   //  │    │
   //  │    └── body: dereference the &u32 to get a u32
   //  └──────── parameter list: one parameter named e (an edge reference)
   
   // Same thing written as a named function:
   fn extract_weight(e: petgraph::graph::EdgeReference<u32>) -> u32 {
       *e.weight()
   }
   
   // You can swap in any cost function you want:
   dijkstra(road, from, None, |e| *e.weight());        // real travel minutes
   dijkstra(road, from, None, |e| *e.weight() * 2);    // every road takes twice as long
   dijkstra(road, from, None, |_| 1u32);               // ignore weights — count hops

3. 03
   Input shape: a directed graph where each node is an intersection and each edge has a u32 weight (travel minutes). Output shape: a HashMap<NodeIndex, u32> — for every node reachable from from, the cheapest total cost to get there. Unreachable nodes are simply absent from the map. Below is a four-intersection example with Dijkstra run from A — notice that D is reached cheaper via A → B → D (cost 3) than via A → C → D (cost 13), and the map records only the winning total.

   Input — &DiGraph<&str, u32>:
   
         A ──2──▶ B ──1──▶ D
         │                 ▲
         5                 8
         │                 │
         ▼                 │
         C ────────────────┘
   
   Edges in the graph:
       A → B   2
       A → C   5
       B → D   1
       C → D   8
   
   
   Call:  dijkstra(road, A, None, |e| *e.weight())
   
   
   Output — HashMap<NodeIndex, u32>:
   
       {
           A → 0,   // start: zero cost to reach yourself
           B → 2,   // A → B
           C → 5,   // A → C
           D → 3,   // A → B → D = 2 + 1   (beats A → C → D = 5 + 8 = 13)
       }