Class DijkstraShortestPath<V,​E>


  • public final class DijkstraShortestPath<V,​E>
    extends java.lang.Object
    An implementation of Dijkstra's shortest path algorithm using ClosestFirstIterator.
    Since:
    Sep 2, 2003
    Author:
    John V. Sichi
    • Constructor Summary

      Constructors 
      Constructor Description
      DijkstraShortestPath​(Graph<V,​E> graph, V startVertex, V endVertex)
      Creates and executes a new DijkstraShortestPath algorithm instance.
      DijkstraShortestPath​(Graph<V,​E> graph, V startVertex, V endVertex, double radius)
      Creates and executes a new DijkstraShortestPath algorithm instance.
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      static <V,​E>
      java.util.List<E>
      findPathBetween​(Graph<V,​E> graph, V startVertex, V endVertex)
      Convenience method to find the shortest path via a single static method call.
      GraphPath<V,​E> getPath()
      Return the path found.
      java.util.List<E> getPathEdgeList()
      Return the edges making up the path found.
      double getPathLength()
      Return the length of the path found.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • DijkstraShortestPath

        public DijkstraShortestPath​(Graph<V,​E> graph,
                                    V startVertex,
                                    V endVertex)
        Creates and executes a new DijkstraShortestPath algorithm instance. An instance is only good for a single search; after construction, it can be accessed to retrieve information about the path found.
        Parameters:
        graph - the graph to be searched
        startVertex - the vertex at which the path should start
        endVertex - the vertex at which the path should end
      • DijkstraShortestPath

        public DijkstraShortestPath​(Graph<V,​E> graph,
                                    V startVertex,
                                    V endVertex,
                                    double radius)
        Creates and executes a new DijkstraShortestPath algorithm instance. An instance is only good for a single search; after construction, it can be accessed to retrieve information about the path found.
        Parameters:
        graph - the graph to be searched
        startVertex - the vertex at which the path should start
        endVertex - the vertex at which the path should end
        radius - limit on path length, or Double.POSITIVE_INFINITY for unbounded search
    • Method Detail

      • getPathEdgeList

        public java.util.List<E> getPathEdgeList()
        Return the edges making up the path found.
        Returns:
        List of Edges, or null if no path exists
      • getPath

        public GraphPath<V,​E> getPath()
        Return the path found.
        Returns:
        path representation, or null if no path exists
      • getPathLength

        public double getPathLength()
        Return the length of the path found.
        Returns:
        path length, or Double.POSITIVE_INFINITY if no path exists
      • findPathBetween

        public static <V,​E> java.util.List<E> findPathBetween​(Graph<V,​E> graph,
                                                                    V startVertex,
                                                                    V endVertex)
        Convenience method to find the shortest path via a single static method call. If you need a more advanced search (e.g. limited by radius, or computation of the path length), use the constructor instead.
        Parameters:
        graph - the graph to be searched
        startVertex - the vertex at which the path should start
        endVertex - the vertex at which the path should end
        Returns:
        List of Edges, or null if no path exists