Class DijkstraAlgorithm

java.lang.Object
org.apache.xmlgraphics.util.dijkstra.DijkstraAlgorithm

public class DijkstraAlgorithm extends 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:
  • Field Details

    • INFINITE

      public static final int INFINITE
      Infinity value for distances.
      See Also:
    • penaltyComparator

      private final Comparator penaltyComparator
      Compares penalties between two possible destinations.
    • edgeDirectory

      private EdgeDirectory edgeDirectory
      The directory of edges
    • priorityQueue

      private TreeSet priorityQueue
      The priority queue for all vertices under inspection, ordered by penalties/distances.
    • finishedVertices

      private Set finishedVertices
      The set of vertices for which the lowest penalty has been found.
    • lowestPenalties

      private Map lowestPenalties
      The currently known lowest penalties for all vertices.
    • predecessors

      private Map predecessors
      Map of all predecessors in the spanning tree of best routes.
  • Constructor Details

    • DijkstraAlgorithm

      public DijkstraAlgorithm(EdgeDirectory edgeDirectory)
      Main Constructor.
      Parameters:
      edgeDirectory - the edge directory this instance should work on
  • Method Details

    • 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 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.