com.tensegrity.graph.algorithm
Class AllPairsShortestPath

java.lang.Object
  com.tensegrity.graph.algorithm.AllPairsShortestPath

public class AllPairsShortestPath

extends java.lang.Object

This class implements the AllPairsShortestPath algorithm variant by Floyd by finding all shortest paths in the graph. That means it will find the shortest path for all possible distinct pairs of nodes.

Version:

$Id: AllPairsShortestPath.java,v 1.14 2006/01/11 13:40:08 MichaelKegel Exp $

Author:

Stepan Rutz

Constructor Summary

AllPairsShortestPath()
Constructs a new stateless instance of the AllPairsShortestPath algorithm.

Method Summary

int[]

apply(Graph graph) Returns a |V| * |V| large 2-dimensional array that represents a matrix of all shortest paths in the graph.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

AllPairsShortestPath

public AllPairsShortestPath()

Constructs a new stateless instance of the AllPairsShortestPath algorithm.

Method Detail

apply

public int[] apply(Graph graph)
            throws GraphException

Returns a |V| * |V| large 2-dimensional array that represents a matrix of all shortest paths in the graph. This is the Floyd version of the APSP algorithm. It is limited to smaller graphs with |V| <= 500. The runtime demand is O(|V|^3) and the space demand is |V|^2.

This algorithm also solves the problem of TransitiveClosure in one go.

For further information consult a text book on graph theory (for example Algorithms in XXX by Sedgewick).

Parameters:

graph - the Graph to analyze, may not be null.

Returns:

two dimensional array of all pairs shortest paths.

Throws:

GraphException - thrown if the algorithm cannot be applied.