Module org.apache.xmlgraphics.commons
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:

  • 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

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

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