Macaulay2 » Documentation
Packages » Graphs :: floydWarshall
next | previous | forward | backward | up | index | toc

floydWarshall -- runs the Floyd-Warshall algorithm on a digraph to determine the minimum distance from one vertex to another in the digraph

Synopsis

Description

The distance from one vertex u to another v in digraph D is the minimum number of edges forming a path from u to v. If v is not reachable from u, the distance is infinity; if u = v, the distance is 0.

i1 : D = digraph({{0,1},{0,2},{2,3},{3,4},{4,2}},EntryMode=>"edges")

o1 = Digraph{0 => {1, 2}}
             1 => {}
             2 => {3}
             3 => {4}
             4 => {2}

o1 : Digraph
i2 : F = floydWarshall D

o2 = HashTable{(0, 0) => 0       }
               (0, 1) => 1
               (0, 2) => 1
               (0, 3) => 2
               (0, 4) => 3
               (1, 0) => infinity
               (1, 1) => 0
               (1, 2) => infinity
               (1, 3) => infinity
               (1, 4) => infinity
               (2, 0) => infinity
               (2, 1) => infinity
               (2, 2) => 0
               (2, 3) => 1
               (2, 4) => 2
               (3, 0) => infinity
               (3, 1) => infinity
               (3, 2) => 2
               (3, 3) => 0
               (3, 4) => 1
               (4, 0) => infinity
               (4, 1) => infinity
               (4, 2) => 1
               (4, 3) => 2
               (4, 4) => 0

o2 : HashTable

See also

Ways to use floydWarshall :

For the programmer

The object floydWarshall is a method function.