Class 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 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.
    • 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 vertex
        end - 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 use getPredecessor(Vertex) to reconstruct the best/shortest path starting from the destination backwards.
        Parameters:
        start - the starting vertex
        destination - 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
      • setPredecessor

        private void setPredecessor​(Vertex a,
                                    Vertex b)
      • 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.
      • getPredecessor

        public Vertex getPredecessor​(Vertex vertex)
        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.