Class Dijkstra<V>

  • Type Parameters:
    V - vertex type
    All Implemented Interfaces:
    ShortestPath<V>

    public class Dijkstra<V>
    extends Object
    implements ShortestPath<V>
    Dijkstra's algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree. This implementation based on a min-priority queue implemented by a Fibonacci heap runs in \(O(|E|+|V|\log|V|)\). It is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs with unbounded non-negative weights.
    See Also:
    Wikipedia: Dijkstra's algorithm
    • Method Detail

      • distance

        public double distance​(V v)
        Description copied from interface: ShortestPath
        Gets the shortest distance from the source to a vertex.
        Specified by:
        distance in interface ShortestPath<V>
        Parameters:
        v - a vertex
        Returns:
        the shortest distance
      • lastEdge

        public WeightedArc<V> lastEdge​(V v)
        Description copied from interface: ShortestPath
        Gets the last edge of a vertex on its shortest distance from the source.
        Specified by:
        lastEdge in interface ShortestPath<V>
        Parameters:
        v - a vertex that is different from the source
        Returns:
        the last edge of a vertex on its shortest distance from the source; null if v is inaccessible from the source