Class DijkstraAlgorithm
java.lang.Object
org.apache.xmlgraphics.util.dijkstra.DijkstraAlgorithm
This is an implementation of Dijkstra's algorithm to find the shortest path for a directed
graph with non-negative edge weights.
- See Also:
-
Field Summary
Fields -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionvoid
Run Dijkstra's shortest path algorithm.protected 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.getPredecessor
(Vertex vertex) Returns the vertex's predecessor on the shortest path.
-
Field Details
-
INFINITE
public static final int INFINITEInfinity value for distances.- See Also:
-
-
Constructor Details
-
DijkstraAlgorithm
Main Constructor.- Parameters:
edgeDirectory
- the edge directory this instance should work on
-
-
Method Details
-
getPenalty
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
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
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
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
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.
-