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 private EdgeDirectory
edgeDirectory
The directory of edgesprivate java.util.Set
finishedVertices
The set of vertices for which the lowest penalty has been found.static int
INFINITE
Infinity value for distances.private java.util.Map
lowestPenalties
The currently known lowest penalties for all vertices.private java.util.Comparator
penaltyComparator
Compares penalties between two possible destinations.private java.util.Map
predecessors
Map of all predecessors in the spanning tree of best routes.private java.util.TreeSet
priorityQueue
The priority queue for all vertices under inspection, ordered by penalties/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.private boolean
isFinished(Vertex v)
Indicates whether a shortest route to a vertex has been found.private void
relax(Vertex u)
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 Detail
-
INFINITE
public static final int INFINITE
Infinity value for distances.- See Also:
- Constant Field Values
-
penaltyComparator
private final java.util.Comparator penaltyComparator
Compares penalties between two possible destinations.
-
edgeDirectory
private EdgeDirectory edgeDirectory
The directory of edges
-
priorityQueue
private java.util.TreeSet priorityQueue
The priority queue for all vertices under inspection, ordered by penalties/distances.
-
finishedVertices
private java.util.Set finishedVertices
The set of vertices for which the lowest penalty has been found.
-
lowestPenalties
private java.util.Map lowestPenalties
The currently known lowest penalties for all vertices.
-
predecessors
private java.util.Map predecessors
Map of all predecessors in the spanning tree of best routes.
-
-
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
-
reset
private void reset()
-
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.
-
relax
private void relax(Vertex u)
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
-
isFinished
private boolean isFinished(Vertex v)
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
private void setShortestDistance(Vertex vertex, int distance)
-
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.
-
-