matrix

Optimized distance matrix computation for subsets of nodes.

This module provides an auto-selecting algorithm for computing shortest path distances between specified “points of interest” (POIs) in a graph. It intelligently chooses between Floyd-Warshall, Johnson’s, and multiple Dijkstra runs based on graph characteristics and POI density.

Algorithm Selection

With negative weights support (when with_subtract is provided):

Algorithm	When Selected	Complexity
Johnson’s	Sparse graphs (E < V²/4)	O(V² log V + VE) then filter
Floyd-Warshall	Dense graphs (E ≥ V²/4)	O(V³) then filter

Without negative weights (when with_subtract is None):

Algorithm	When Selected	Complexity
Dijkstra × P	Few POIs (P ≤ V/3)	O(P × (V + E) log V)
Floyd-Warshall	Many POIs (P > V/3)	O(V³) then filter

Heuristics

For graphs with potential negative weights:

Johnson’s algorithm is preferred for sparse graphs where E < V²/4
Floyd-Warshall is preferred for denser graphs

For non-negative weights only:

Multiple Dijkstra runs when P ≤ V/3 (few POIs)
Floyd-Warshall when P > V/3 (many POIs)

Use Cases

Game AI: Pathfinding between key locations (not all nodes)
Logistics: Distance matrix for delivery stops
Facility location: Distances between candidate sites
Network analysis: Selected node pairwise distances

Example

// Compute distances only between important waypoints
let pois = [start, waypoint_a, waypoint_b, goal]
let distances = matrix.distance_matrix(
  in: graph,
  between: pois,
  with_zero: 0,
  with_add: int.add,
  with_compare: int.compare,
)
// Result contains only 4×4 = 16 distances, not full V×V matrix

References

See yog/pathfinding/floyd_warshall for all-pairs algorithm details (O(V³))
See yog/pathfinding/johnson for sparse all-pairs with negative weights (O(V² log V + VE))
See yog/pathfinding/dijkstra for single-source algorithm details (O((V+E) log V))

Values

distance_matrix

</>

pub fn distance_matrix(
  in graph: model.Graph(n, e),
  between points_of_interest: List(Int),
  with_zero zero: e,
  with_add add: fn(e, e) -> e,
  with_subtract subtract: option.Option(fn(e, e) -> e),
  with_compare compare: fn(e, e) -> order.Order,
) -> Result(dict.Dict(#(Int, Int), e), Nil)

Computes shortest distances between all pairs of points of interest.

Automatically chooses the best algorithm based on:

Whether negative weights are possible (presence of with_subtract)
Graph sparsity (E relative to V²)
POI density (P relative to V)

Time Complexity: O(V³), O(V² log V + VE), or O(P × (V + E) log V)

Parameters

with_subtract: Optional subtraction function for negative weight support. If provided, enables Johnson’s algorithm for sparse graphs with negative weights. If None, assumes non-negative weights and may use Dijkstra.

Examples

// Non-negative weights only (uses Dijkstra or Floyd-Warshall)
matrix.distance_matrix(
  in: graph,
  between: pois,
  with_zero: 0,
  with_add: int.add,
  with_subtract: None,
  with_compare: int.compare,
)

// Support negative weights (uses Johnson's or Floyd-Warshall)
matrix.distance_matrix(
  in: graph,
  between: pois,
  with_zero: 0,
  with_add: int.add,
  with_subtract: Some(int.subtract),
  with_compare: int.compare,
)