next | previous | forward | backward | up | top | index | toc | Macaulay2 web site

allPairsShortestPath -- computes lengths of shortest paths between all pairs in a directed graph

Synopsis

Description

This function uses the Floyd-Warshall algorithm to compute the lengths of shortest paths between all pairs of vertices in a directed graph.
i1 : G = directedGraph( {a,b,c,d,e}, {(a,b),(b,c),(a,c),(a,d),(d,e)});
i2 : allPairsShortestPath(G)

o2 = | 0        1        1        1        2        |
     | infinity 0        1        infinity infinity |
     | infinity infinity 0        infinity infinity |
     | infinity infinity infinity 0        1        |
     | infinity infinity infinity infinity 0        |

                5          5
o2 : Matrix RR    <--- RR
              53         53
i3 : allPairsShortestPath(adjacencyMatrix(G))

o3 = | 0        1        1        1        2        |
     | infinity 0        1        infinity infinity |
     | infinity infinity 0        infinity infinity |
     | infinity infinity infinity 0        1        |
     | infinity infinity infinity infinity 0        |

                5          5
o3 : Matrix RR    <--- RR
              53         53
i4 : A = matrix({{0,1,3,5},{1/0.,0,1,3},{1/0.,1/0.,0,1},{2,1/0.,1/0.,0}})

o4 = | 0        1        3        5 |
     | infinity 0        1        3 |
     | infinity infinity 0        1 |
     | 2        infinity infinity 0 |

                4          4
o4 : Matrix RR    <--- RR
              53         53
i5 : allPairsShortestPath(A)

o5 = | 0 1 2 3 |
     | 4 0 1 2 |
     | 3 4 0 1 |
     | 2 3 4 0 |

                4          4
o5 : Matrix RR    <--- RR
              53         53

Caveat

Assume there is no negative cycles. Output matrix is over RR.

See also

Ways to use allPairsShortestPath :