Class DijkstraAlgorithm
- java.lang.Object
-
- 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
Fields Modifier and Type Field Description static int
INFINITE
Infinity value for distances.
-
Constructor Summary
Constructors Constructor Description DijkstraAlgorithm(EdgeDirectory edgeDirectory)
Main Constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description 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.
-
-
-
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 vertexend
- 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 usegetPredecessor(Vertex)
to reconstruct the best/shortest path starting from the destination backwards.- Parameters:
start
- the starting vertexdestination
- 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.
-
-