Package org.apache.xmlgraphics.util.dijkstra

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
      static int INFINITE
      Infinity value for distances.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method 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.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Field Detail

      • INFINITE

        public static final int INFINITE
        Infinity value for distances.
        See Also:
        Constant Field Values

    • 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

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