|
xmlgraphics-commons 1.3 | |||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.apache.xmlgraphics.util.dijkstra.DijkstraAlgorithm
public class DijkstraAlgorithm
This is an implementation of Dijkstra's algorithm to find the shortest path for a directed graph with non-negative edge weights.
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 |
---|
public static final int INFINITE
Constructor Detail |
---|
public DijkstraAlgorithm(EdgeDirectory edgeDirectory)
edgeDirectory
- the edge directory this instance should work onMethod Detail |
---|
protected int getPenalty(Vertex start, Vertex end)
start
- the start vertexend
- the end vertex
protected java.util.Iterator getDestinations(Vertex origin)
origin
- the origin from which to search for destinations
public void execute(Vertex start, Vertex destination)
getPredecessor(Vertex)
to reconstruct the best/shortest path starting from the
destination backwards.
start
- the starting vertexdestination
- the destination vertex.public int getLowestPenalty(Vertex vertex)
vertex
- the vertex
INFINITE
if there is no route to
the destination.public Vertex getPredecessor(Vertex vertex)
vertex
- the vertex for which to find the predecessor
null
if there is no route to the destination.
|
xmlgraphics-commons 1.3 | |||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |