380: Weighted Graph and Dijkstra

Difficulty: 3 Level: Advanced Graphs with edge costs, and Dijkstra's algorithm for shortest paths.

The Problem This Solves

Real graphs have costs. Road networks have distances. Network topologies have latencies. Dependency graphs have build times. You need not just "is there a path?" but "what is the cheapest path?" — and for non-negative edge weights, Dijkstra's algorithm answers this in `O((V + E) log V)`. This is the algorithm behind Google Maps routing, IP routing protocols (OSPF), game AI pathfinding (with a heuristic it becomes A*), and any optimization problem that can be framed as shortest path. If you've ever called `.shortest_path()` in any framework, something like Dijkstra is running underneath.

The Intuition

Dijkstra maintains a priority queue of `(cost, node)` pairs, always expanding the cheapest-to-reach node first. Start with source node at cost 0. For each expanded node, check all its neighbors: if the path through this node is cheaper than the currently known best path to that neighbor, update and enqueue. Repeat until the queue is empty or you've found your target. The key insight: once you pop a node from the priority queue, you've found the cheapest path to it. You never need to revisit it. This greedy property holds because all edge weights are non-negative. Negative edges break Dijkstra — use Bellman-Ford instead. Rust's `BinaryHeap` is a max-heap; wrap costs in `std::cmp::Reverse` to get a min-heap.

How It Works in Rust

use std::collections::{BinaryHeap, HashMap};
use std::cmp::Reverse;

type Graph = HashMap<usize, Vec<(usize, u32)>>; // node → [(neighbor, cost)]

fn dijkstra(graph: &Graph, start: usize) -> HashMap<usize, u32> {
 let mut dist: HashMap<usize, u32> = HashMap::new();
 let mut heap = BinaryHeap::new();

 dist.insert(start, 0);
 heap.push(Reverse((0u32, start)));

 while let Some(Reverse((cost, node))) = heap.pop() {
     if cost > *dist.get(&node).unwrap_or(&u32::MAX) {
         continue; // already found a cheaper path
     }
     for &(neighbor, edge_cost) in graph.get(&node).unwrap_or(&vec![]) {
         let new_cost = cost + edge_cost;
         if new_cost < *dist.get(&neighbor).unwrap_or(&u32::MAX) {
             dist.insert(neighbor, new_cost);
             heap.push(Reverse((new_cost, neighbor)));
         }
     }
 }
 dist
}

For production use: `petgraph::algo::dijkstra` with full graph API support.

What This Unlocks

Routing algorithms — GPS navigation, network packet routing, flight path optimization.
Game AI — A* is Dijkstra with a heuristic; pathfinding on grids, navmeshes, and graphs.
Build optimization — schedule tasks on the critical path of a weighted task DAG.

Key Differences

Concept	OCaml	Rust
Priority queue	`Set` (balanced BST, acts as heap)	`BinaryHeap<T>` (max-heap; use `Reverse` for min)
Weighted graph	Manual adjacency with weights	`HashMap<usize, Vec<(usize, u32)>>` or `petgraph`
Dijkstra	`ocamlgraph` or manual	`petgraph::algo::dijkstra` or manual
Negative weights	Bellman-Ford via `ocamlgraph`	`petgraph::algo::bellman_ford`

// Weighted graph and Dijkstra in Rust
use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn dijkstra(adj: &[Vec<(usize, u64)>], n: usize, src: usize) -> Vec<u64> {
    let mut dist = vec![u64::MAX; n];
    dist[src] = 0;
    // Min-heap: (distance, vertex)
    let mut heap = BinaryHeap::new();
    heap.push(Reverse((0u64, src)));

    while let Some(Reverse((d, u))) = heap.pop() {
        if d > dist[u] { continue; } // stale entry
        for &(v, w) in &adj[u] {
            let nd = dist[u].saturating_add(w);
            if nd < dist[v] {
                dist[v] = nd;
                heap.push(Reverse((nd, v)));
            }
        }
    }
    dist
}

fn main() {
    let n = 5;
    let mut adj = vec![vec![]; n];
    let edges = [(0,1,10u64),(0,2,3),(1,3,2),(2,1,4),(2,3,8),(2,4,2),(3,4,5),(4,3,7)];
    for (u, v, w) in edges {
        adj[u].push((v, w));
    }
    let dist = dijkstra(&adj, n, 0);
    println!("Shortest distances from vertex 0:");
    for (v, d) in dist.iter().enumerate() {
        if *d == u64::MAX {
            println!("  to {}: inf", v);
        } else {
            println!("  to {}: {}", v, d);
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_dijkstra() {
        let n = 4;
        let mut adj = vec![vec![]; n];
        adj[0].push((1, 1u64));
        adj[0].push((2, 4));
        adj[1].push((2, 2));
        adj[1].push((3, 5));
        adj[2].push((3, 1));
        let dist = dijkstra(&adj, n, 0);
        assert_eq!(dist[0], 0);
        assert_eq!(dist[1], 1);
        assert_eq!(dist[2], 3);
        assert_eq!(dist[3], 4);
    }
}

(* Dijkstra's shortest path in OCaml *)
(* Priority queue via sorted list (simple but not optimal) *)

let dijkstra adj n src =
  let inf = max_int in
  let dist = Array.make n inf in
  let visited = Array.make n false in
  dist.(src) <- 0;
  let pq = ref [(0, src)] in
  while !pq <> [] do
    let (d, u) = List.hd !pq in
    pq := List.tl !pq;
    if not visited.(u) then begin
      visited.(u) <- true;
      List.iter (fun (v, w) ->
        if dist.(u) <> inf && dist.(u) + w < dist.(v) then begin
          dist.(v) <- dist.(u) + w;
          pq := List.sort compare ((dist.(v), v) :: !pq)
        end
      ) adj.(u)
    end
  done;
  dist

let () =
  let n = 5 in
  let adj = Array.make n [] in
  let edges = [(0,1,10);(0,2,3);(1,3,2);(2,1,4);(2,3,8);(2,4,2);(3,4,5);(4,3,7)] in
  List.iter (fun (u,v,w) -> adj.(u) <- (v,w) :: adj.(u)) edges;
  let dist = dijkstra adj n 0 in
  Printf.printf "Shortest distances from vertex 0:\n";
  Array.iteri (fun v d ->
    if d = max_int then Printf.printf "  to %d: inf\n" v
    else Printf.printf "  to %d: %d\n" v d
  ) dist