程序包 edu.princeton.cs.algs4

类 DijkstraUndirectedSP

  • public class DijkstraUndirectedSP
extends java.lang.Object
    The DijkstraUndirectedSP class represents a data type for solving the single-source shortest paths problem in edge-weighted graphs where the edge weights are nonnegative.

    This implementation uses Dijkstra's algorithm with a binary heap. The constructor takes time proportional to E log V, where V is the number of vertices and E is the number of edges. Each call to distTo(int) and hasPathTo(int) takes constant time; each call to pathTo(int) takes time proportional to the number of edges in the shortest path returned.

    For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. See DijkstraSP for a version on edge-weighted digraphs.

    • 构造器概要

      构造器 
      构造器 说明
      DijkstraUndirectedSP​(EdgeWeightedGraph G, int s)
      Computes a shortest-paths tree from the source vertex s to every other vertex in the edge-weighted graph G.

    • 方法概要

      修饰符和类型 方法 说明
      double distTo​(int v)
      Returns the length of a shortest path between the source vertex s and vertex v.
      boolean hasPathTo​(int v)
      Returns true if there is a path between the source vertex s and vertex v.
      static void main​(java.lang.String[] args)
      Unit tests the DijkstraUndirectedSP data type.
      java.lang.Iterable<Edge> pathTo​(int v)
      Returns a shortest path between the source vertex s and vertex v.

      • 从类继承的方法 java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • 构造器详细资料

      • DijkstraUndirectedSP

        public DijkstraUndirectedSP​(EdgeWeightedGraph G,
                            int s)
        Computes a shortest-paths tree from the source vertex s to every other vertex in the edge-weighted graph G.
        参数:
        G - the edge-weighted digraph
        s - the source vertex
        抛出:
        java.lang.IllegalArgumentException - if an edge weight is negative
        java.lang.IllegalArgumentException - unless 0 <= s < V

    • 方法详细资料

      • distTo

        public double distTo​(int v)
        Returns the length of a shortest path between the source vertex s and vertex v.
        参数:
        v - the destination vertex
        返回:
        the length of a shortest path between the source vertex s and the vertex v; Double.POSITIVE_INFINITY if no such path
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= v < V

      • hasPathTo

        public boolean hasPathTo​(int v)
        Returns true if there is a path between the source vertex s and vertex v.
        参数:
        v - the destination vertex
        返回:
        true if there is a path between the source vertex s to vertex v; false otherwise
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= v < V

      • pathTo

        public java.lang.Iterable<Edge> pathTo​(int v)
        Returns a shortest path between the source vertex s and vertex v.
        参数:
        v - the destination vertex
        返回:
        a shortest path between the source vertex s and vertex v; null if no such path
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= v < V

      • main

        public static void main​(java.lang.String[] args)
        Unit tests the DijkstraUndirectedSP data type.
        参数:
        args - the command-line arguments