Class DijkstraShortestPathFinder

Object
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 Details

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

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

      public DijkstraIterator getIterator()
    • getTraversal

      public GraphTraversal getTraversal()
    • 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:
    • finish

      public void finish()
      Does nothing.
      Specified by:
      finish in interface GraphWalker
      See Also: