DistanceMatrix (yog-fsharp)

DistanceMatrix Module

Namespace: Yog.Pathfinding
Assembly: Yog.FSharp.dll

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 chooses between Floyd-Warshall and multiple Dijkstra runs based on POI density.

Algorithm Selection

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

Heuristic

The crossover point is P > V/3 where P is the number of points of interest: - Dense POIs: Floyd-Warshall computes all-pairs once, then filter - Sparse POIs: Run Dijkstra from each POI individually

This heuristic balances the O(V³) Floyd-Warshall against the O(P(V+E) log V) cost of multiple Dijkstra runs.

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

Functions and values

Function or value	Description
`distanceMatrix zero add compare pois graph` Full Usage: `distanceMatrix zero add compare pois graph` Parameters: zero : `'e` add : `'e -> 'e -> 'e` compare : `'e -> 'e -> int` pois : `NodeId list` graph : `Graph<'n, 'e>` Returns: `Result<Map<(NodeId * NodeId), 'e>, unit>`	Computes shortest distances between all pairs of points of interest. Automatically chooses between Floyd-Warshall and multiple Dijkstra runs based on the density of POIs relative to graph size. Time Complexity: O(V³) or O(P * (V + E) log V) zero : `'e` add : `'e -> 'e -> 'e` compare : `'e -> 'e -> int` pois : `NodeId list` graph : `Graph<'n, 'e>` Returns: `Result<Map<(NodeId * NodeId), 'e>, unit>`
`distanceMatrixFloat pois graph` Full Usage: `distanceMatrixFloat pois graph` Parameters: pois : `NodeId list` graph : `Graph<'n, float>` Returns: `Result<Map<(NodeId * NodeId), float>, unit>`	Computes POI distance matrix using float weights. pois : `NodeId list` graph : `Graph<'n, float>` Returns: `Result<Map<(NodeId * NodeId), float>, unit>`
`distanceMatrixInt pois graph` Full Usage: `distanceMatrixInt pois graph` Parameters: pois : `NodeId list` graph : `Graph<'n, int>` Returns: `Result<Map<(NodeId * NodeId), int>, unit>`	Computes POI distance matrix using integer weights. pois : `NodeId list` graph : `Graph<'n, int>` Returns: `Result<Map<(NodeId * NodeId), int>, unit>`