Package org.apache.xmlgraphics.util.dijkstra

Class 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:
    WikiPedia on Dijkstra's Algorithm

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