Nettle.Topology.FloydWarshall

Implements the Floyd-Warshall algorithm for computing all-pairs shortest paths from a weighted directed graph.

Documentation

floydWarshall :: Array (Int, Int) (ExtendedDouble, Maybe (Int, a)) -> Array (Int, Int) (ExtendedDouble, Maybe (Int, a))

The input is a matrix where the (i,j) entry contains the distance of a path going from node i to node j in the graph as well as the next hop node in the path and a value (left polymorphic, of type a here) representing the link (e.g. a link identifier, particularly useful if there can more than one link between nodes). If the distance is |Infinity| then the next hop and link identifier should be |Nothing|. Typically, this function is applied to an array in which (i,j) value contains the distance and the link ID for one link from i to j.

shortestPath :: Array (Int, Int) (ExtendedDouble, Maybe (Int, a)) -> (Int, Int) -> Maybe [(Int, a)]

Extracts the shortest path from the matrix computed by |floydWarshall|. The path includes the the nodes and the links of the path.