Class DijkstraShortestPathFinder

  • All Implemented Interfaces:
    GraphWalker

    public class DijkstraShortestPathFinder
    extends Object
    implements GraphWalker
    Calculates node paths in a graph using Dijkstra's Shortest Path Algorithm. Dijsktras algorithm calculates a shortest path from a specefied node (the source node of the underlying dijkstra iteration) to every other node in the graph.
    Author:
    Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
    See Also:
    DijsktraIterator
    • Constructor Detail

      • DijkstraShortestPathFinder

        public DijkstraShortestPathFinder​(Graph graph,
                                          DijkstraIterator iterator)
        Constructs a new path finder.
        Parameters:
        graph - The graph to calculate paths for.
        iterator - The dijsktra iterator to used to calculate shortest paths.
      • DijkstraShortestPathFinder

        public DijkstraShortestPathFinder​(Graph graph,
                                          Graphable source,
                                          DijkstraIterator.EdgeWeighter weighter)
        Constructs a new path finder.
        Parameters:
        graph - Graph to calculate paths for.
        source - Node to calculate paths from.
        weighter - Associates weights with edges in the graph.
      • DijkstraShortestPathFinder

        public DijkstraShortestPathFinder​(Graph graph,
                                          Graphable source,
                                          DijkstraIterator.EdgeWeighter weighter,
                                          DijkstraIterator.NodeWeighter nweighter)
        Constructs a new path finder.
        Parameters:
        graph - Graph to calculate paths for.
        source - Node to calculate paths from.
        weighter - Associates weights with edges in the graph.
        nweighter - Associates weights with nodes in the graph.
    • Method Detail

      • calculate

        public void calculate()
        Performs the graph traversal and calculates the shortest path from the source node to every other node in the graph.
      • getPath

        public Path getPath​(Graphable g)
        Returns a path from g to the source. If the desired path is the opposite (from the source to g) can be used.
        Parameters:
        g - The start node of the path to be calculated.
        Returns:
        A path from g to the source.
        See Also:
        Walk.riterator()
      • getCost

        public double getCost​(Graphable g)
        Returns the cost associated with a node calculated during the graph traversal.
        Parameters:
        g - The node whose cost is desired.
        Returns:
        The cost associated with the node.
      • visit

        public int visit​(Graphable element,
                         GraphTraversal traversal)
        Does nothing except signal the traversal to continue.
        Specified by:
        visit in interface GraphWalker
        Parameters:
        element - The component being visited.
        traversal - The traversal controlling the sequence of graph component visits.
        Returns:
        GraphTraversal#CONTINUE to signal that the traversal should continue.
        GraphTraversal#CONTINUE to signal that the traversal should suspend.
        GraphTraversal#KILL_BRANCH to signal that the traversal should kill its current branch.
        GraphTraversal#STOP to signal that the traversal should stop.
        See Also:
        GraphWalker.visit(Graphable, GraphTraversal)