Package org.apache.xmlgraphics.util.dijkstra

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.