xmlgraphics-commons 1.3

org.apache.xmlgraphics.util.dijkstra
Class DijkstraAlgorithm

java.lang.Object
  extended by org.apache.xmlgraphics.util.dijkstra.DijkstraAlgorithm

public class DijkstraAlgorithm
extends java.lang.Object

This is an implementation of Dijkstra's algorithm to find the shortest path for a directed graph with non-negative edge weights.

See Also:
WikiPedia on Dijkstra's Algorithm

Field Summary
static int INFINITE
          Infinity value for distances.
 
Constructor Summary
DijkstraAlgorithm(EdgeDirectory edgeDirectory)
          Main Constructor.
 
Method Summary
 void execute(Vertex start, Vertex destination)
          Run Dijkstra's shortest path algorithm.
protected  java.util.Iterator getDestinations(Vertex origin)
          Returns an iterator over all valid destinations for a given vertex.
 int getLowestPenalty(Vertex vertex)
          Returns the lowest penalty from the start point to a given vertex.
protected  int getPenalty(Vertex start, Vertex end)
          Returns the penalty between two vertices.
 Vertex getPredecessor(Vertex vertex)
          Returns the vertex's predecessor on the shortest path.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

INFINITE

public static final int INFINITE
Infinity value for distances.

See Also:
Constant Field Values
Constructor Detail

DijkstraAlgorithm

public DijkstraAlgorithm(EdgeDirectory edgeDirectory)
Main Constructor.

Parameters:
edgeDirectory - the edge directory this instance should work on
Method Detail

getPenalty

protected int getPenalty(Vertex start,
                         Vertex end)
Returns the penalty between two vertices.

Parameters:
start - the start vertex
end - the end vertex
Returns:
the penalty between two vertices, or 0 if no single edge between the two vertices exists.

getDestinations

protected java.util.Iterator getDestinations(Vertex origin)
Returns an iterator over all valid destinations for a given vertex.

Parameters:
origin - the origin from which to search for destinations
Returns:
the iterator over all valid destinations for a given vertex

execute

public void execute(Vertex start,
                    Vertex destination)
Run Dijkstra's shortest path algorithm. After this method is finished you can use getPredecessor(Vertex) to reconstruct the best/shortest path starting from the destination backwards.

Parameters:
start - the starting vertex
destination - the destination vertex.

getLowestPenalty

public int getLowestPenalty(Vertex vertex)
Returns the lowest penalty from the start point to a given vertex.

Parameters:
vertex - the vertex
Returns:
the lowest penalty or INFINITE if there is no route to the destination.

getPredecessor

public Vertex getPredecessor(Vertex vertex)
Returns the vertex's predecessor on the shortest path.

Parameters:
vertex - the vertex for which to find the predecessor
Returns:
the vertex's predecessor on the shortest path, or null if there is no route to the destination.

xmlgraphics-commons 1.3

Copyright 1999-2008 The Apache Software Foundation. All Rights Reserved.