HMath.Graph.Paths¶
Module index · Numerical conventions
Description
Checked graph paths. Unreachable distances are Nothing. A reachable
negative cycle is a domain error; all-pairs methods reject any negative cycle.
Nonfinite arithmetic is rejected. Dijkstra-family methods require nonnegative
weights. Returned vertex paths use lexicographic tie-breaking where applicable.
On this page¶
| API | Purpose |
|---|---|
| dijkstra | Given graph then source, return minimum distances in vertex order, with Nothing for unreachable vertices. |
| multiSourceDijkstra | Given graph then source list, return distance to the nearest supplied source, each seeded at zero. |
| bellmanFord | Given graph then source, return minimum distances including negative weights. |
| floydWarshall | Return all-pairs minimum-distance rows, with Nothing for unreachable pairs. |
| johnson | Johnson reweighting: Bellman--Ford potentials from an implicit zero-cost super-source, followed by independent Dijkstra searches. |
| aStar | A* requires a finite consistent heuristic, h(target)=0, checked on all arcs. |
| bidirectionalDijkstra | Two settled-frontier Dijkstra searches, alternating the frontier with the smaller minimum key. |
| kShortestPaths | K cheapest simple vertex paths, best-first expansion, for nonnegative weights. |
| longestDAGPaths | Given directed acyclic graph then source, return maximum path-weight distance to each vertex, Nothing for unreachable vertices. |
Documentation
dijkstra
dijkstra :: Graph -> Int -> Either MathError [Maybe Double] Source #
Given graph then source, return minimum distances in vertex order, with Nothing for unreachable vertices. Require valid source and nonnegative weights; invalid input or non-finite arithmetic fails.
multiSourceDijkstra
multiSourceDijkstra :: Graph -> [Int] -> Either MathError [Maybe Double] Source #
Given graph then source list, return distance to the nearest supplied source, each seeded at zero. Invalid sources, negative weights or non-finite arithmetic fail. Empty sources give all Nothing.
bellmanFord
bellmanFord :: Graph -> Int -> Either MathError [Maybe Double] Source #
Given graph then source, return minimum distances including negative weights. Invalid source, reachable negative cycle or non-finite arithmetic returns Left MathError; unreachable vertices are Nothing.
floydWarshall
floydWarshall :: Graph -> Either MathError [[Maybe Double]] Source #
Return all-pairs minimum-distance rows, with Nothing for unreachable pairs. Negative edges are allowed; any negative cycle or non-finite arithmetic fails.
johnson
johnson :: Graph -> Either MathError [[Maybe Double]] Source #
Johnson reweighting: Bellman--Ford potentials from an implicit zero-cost super-source, followed by independent Dijkstra searches.
aStar
aStar :: Graph -> (Int -> Double) -> Int -> Int -> Either MathError (Maybe (Double, [Int])) Source #
A* requires a finite consistent heuristic, h(target)=0, checked on all arcs. This guarantees optimality without trusting an arbitrary heuristic.
bidirectionalDijkstra
bidirectionalDijkstra :: Graph -> Int -> Int -> Either MathError (Maybe Double) Source #
Two settled-frontier Dijkstra searches, alternating the frontier with the smaller minimum key. The best meeting bound stops the search safely.
kShortestPaths
kShortestPaths :: Int -> Int -> Graph -> Int -> Int -> Either MathError [(Double, [Int], [Int])] Source #
K cheapest simple vertex paths, best-first expansion, for nonnegative weights. Parallel edges generate distinct edge paths; output includes edge IDs to preserve this identity. Fuel counts expanded partial paths.