haccepted-0.1.0.0: Data structures and algorithms
Safe HaskellNone
LanguageHaskell2010

FloydWarshall

Description

Floyd-Warshall algorithm

Finds shortest paths between all pairs of vertices in a directed weighted graph.

Sources:

Synopsis

Documentation

data WEdge Source #

Constructors

WEdge !Vertex !Vertex !Weight 

Instances

Instances details
Eq WEdge Source # 
Instance details

Defined in FloydWarshall

Methods

(==) :: WEdge -> WEdge -> Bool #

(/=) :: WEdge -> WEdge -> Bool #

Show WEdge Source # 
Instance details

Defined in FloydWarshall

Methods

showsPrec :: Int -> WEdge -> ShowS #

show :: WEdge -> String #

showList :: [WEdge] -> ShowS #

type Weight = Int Source #

floydWarshallFromEdges :: Bounds -> [WEdge] -> Vertex -> Vertex -> Maybe Weight Source #

Runs the algorithm on the graph represented by the given list of edges. There should be no negative cycles. O(|V|^3). Queries take O(1).

floydWarshall :: MArray a Weight m => a (Vertex, Vertex) Weight -> m () Source #

Runs the algorithm on the adjacency matrix of the graph given as a mutable array. O(|V|^3).