com.tensegrity.graph.algorithm
Class SingleSourceShortestPath

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

public class SingleSourceShortestPath

extends java.lang.Object

This class implements the single-source shortest path (SSSP) algorithm by finding a path between two vertices such that the sum of the weights of its constituent edges is minimized.

Version:

$Id: SingleSourceShortestPath.java,v 1.17 2006/01/11 13:47:47 MichaelKegel Exp $

Author:

Stepan Rutz, MichaelKegel

Constructor Summary

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

Method Summary

int[]	apply(Graph graph, Node node) This algorithm will return an integer array of length |V| (number of nodes in the graph) that has the path costs to all nodes from the given start node.
java.util.Map	generatePathMap(Graph graph, Node node)

Methods inherited from class java.lang.Object

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

Constructor Detail

SingleSourceShortestPath

public SingleSourceShortestPath()

Constructs a new stateless instance of the SingleSourceShortestPath algorithm.

Method Detail

apply

public int[] apply(Graph graph,
                   Node node)
            throws GraphException

This algorithm will return an integer array of length |V| (number of nodes in the graph) that has the path costs to all nodes from the given start node. Algorithm runtime is O(|V|^2)

Parameters:

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

node - the Node to examine, may not be null.

Returns:

an array of the shortest path distances to all the nodes in the given graph starting from the given node.

Throws:

GraphException - thrown if the algorithm cannot be applied.

generatePathMap

public java.util.Map generatePathMap(Graph graph,
                                     Node node)
                              throws GraphException

Throws:

GraphException