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
FieldsModifier and TypeFieldDescriptionprivate EdgeDirectory
The directory of edgesprivate Set
The set of vertices for which the lowest penalty has been found.static final int
Infinity value for distances.private Map
The currently known lowest penalties for all vertices.private final Comparator
Compares penalties between two possible destinations.private Map
Map of all predecessors in the spanning tree of best routes.private TreeSet
The priority queue for all vertices under inspection, ordered by penalties/distances. -
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.private boolean
isFinished
(Vertex v) Indicates whether a shortest route to a vertex has been found.private void
Compute new lowest penalties for neighboring vertices.private void
reset()
private void
setPredecessor
(Vertex a, Vertex b) private void
setShortestDistance
(Vertex vertex, int distance)
-
Field Details
-
INFINITE
public static final int INFINITEInfinity value for distances.- See Also:
-
penaltyComparator
Compares penalties between two possible destinations. -
edgeDirectory
The directory of edges -
priorityQueue
The priority queue for all vertices under inspection, ordered by penalties/distances. -
finishedVertices
The set of vertices for which the lowest penalty has been found. -
lowestPenalties
The currently known lowest penalties for all vertices. -
predecessors
Map of all predecessors in the spanning tree of best routes.
-
-
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
-
reset
private void reset() -
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.
-
relax
Compute new lowest penalties for neighboring vertices. Update the lowest penalties and the predecessor map if a better solution is found.- Parameters:
u
- the vertex to process
-
setPredecessor
-
isFinished
Indicates whether a shortest route to a vertex has been found.- Parameters:
v
- the vertex- Returns:
- true if the shortest route to this vertex has been found.
-
setShortestDistance
-
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.
-