algorithm requires time and space in the worst case. This algorithm is not solely interested in reachability as it also computes the shortest path distance between all pairs of vertices. For graphs containing negative cycles, shortest paths may be undefined, but reachability between pairs can still be noted.

Thorup's Algorithm

For planar digraphs, a much faster method is available, as described by Mikkel Thorup

1.Previous
3.Next