hgeometry-combinatorial-0.12.0.0: Data structures, and Data types.
Copyright(C) David Himmelstrup
Licensesee the LICENSE file
MaintainerDavid Himmelstrup
Safe HaskellNone
LanguageHaskell2010

Algorithms.FloydWarshall

Description

Implementation of Floyd-Warshall shortest path algorithm.

See Wikipedia article for details: https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

Synopsis

Documentation

mkIndex :: Num a => a -> (a, a) -> a Source #

Compute the index of an element in a given range.

mkGraph :: (Unbox a, Num a) => Int -> a -> [(Int, Int, a)] -> ST s (MVector s (a, Int)) Source #

Construct a weighted graph from \(n\) vertices, a max bound, and a list of weighted edges.

floydWarshall :: (Unbox a, Fractional a, Ord a) => Int -> MVector s (a, Int) -> ST s () Source #

\( O(n^3) \)