🗺️ Dijkstra's Shortest Path

Weighted graphs, priority queues, and shortest path algorithms

Overview

Implements Dijkstra's algorithm for single-source shortest paths in weighted graphs, plus Floyd-Warshall for all-pairs shortest paths and Prim's algorithm for minimum spanning trees.

Concepts Demonstrated

Weighted adjacency lists — IntMap-based graph representation
Priority queues — sorted-list implementation for educational clarity
Dijkstra's algorithm — greedy BFS with distance relaxation
Floyd-Warshall — dynamic programming on all vertex pairs
Prim's MST — greedy minimum spanning tree construction
Path reconstruction — predecessor tracking for route recovery
Hash tables — mutable state for O(1) distance lookups

Key Functions

Function	Description
`dijkstra`	Single-source shortest paths from a vertex
`shortest_distance`	Distance between two specific vertices
`shortest_path`	Full path + distance between two vertices
`floyd_warshall`	All-pairs shortest paths (O(V³))
`prim_mst`	Minimum spanning tree (undirected graphs)
`add_edge`	Add a weighted edge (handles direction)

Graph Representation

type weighted_graph = {
  adj: (int * float) list IntMap.t;  (* vertex → [(neighbor, weight)] *)
  directed: bool;
}

(* Build a graph *)
let g = empty_graph ~directed:false
  |> add_edge 0 1 4.0
  |> add_edge 0 2 1.0
  |> add_edge 2 1 2.0

Algorithm Walkthrough

(* Dijkstra's: greedily expand nearest unvisited vertex *)
(* 1. Start: dist[source] = 0, all others = ∞ *)
(* 2. Pick unvisited vertex u with smallest dist[u] *)
(* 3. For each neighbor v: relax edge if dist[u]+w < dist[v] *)
(* 4. Mark u visited; repeat until queue empty *)

let (dist, prev) = dijkstra g 0 in
shortest_path g 0 3
(* → Some ([0; 2; 1; 3], 7.0) *)