public class DijkstraAlgorithm
extends java.lang.Object
Modifier and Type | Field and Description |
---|---|
private EdgeDirectory |
edgeDirectory
The directory of edges
|
private 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 and Description |
---|
DijkstraAlgorithm(EdgeDirectory edgeDirectory)
Main Constructor.
|
Modifier and Type | Method and 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) |
public static final int INFINITE
private final java.util.Comparator penaltyComparator
private EdgeDirectory edgeDirectory
private java.util.TreeSet priorityQueue
private java.util.Set finishedVertices
private java.util.Map lowestPenalties
private java.util.Map predecessors
public DijkstraAlgorithm(EdgeDirectory edgeDirectory)
edgeDirectory
- the edge directory this instance should work onprotected int getPenalty(Vertex start, Vertex end)
start
- the start vertexend
- the end vertexprotected java.util.Iterator getDestinations(Vertex origin)
origin
- the origin from which to search for destinationsprivate void reset()
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.private void relax(Vertex u)
u
- the vertex to processprivate boolean isFinished(Vertex v)
v
- the vertexprivate void setShortestDistance(Vertex vertex, int distance)
public int getLowestPenalty(Vertex vertex)
vertex
- the vertexINFINITE
if there is no route to
the destination.