Algorithms.FloydWarshall

Description

Implementation of Floyd-Warshall shortest path algorithm.

Synopsis

mkIndex :: Num a => a -> (a, a) -> a
mkGraph :: (Unbox a, Num a) => Int -> a -> [(Int, Int, a)] -> ST s (MVector s (a, Int))
floydWarshall :: (Unbox a, Fractional a, Ord a) => Int -> MVector s (a, Int) -> ST s ()

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.

$O(n^3)$