程序包 edu.princeton.cs.algs4

类 AcyclicSP

  • public class AcyclicSP
extends java.lang.Object
    The AcyclicSP class represents a data type for solving the single-source shortest paths problem in edge-weighted directed acyclic graphs (DAGs). The edge weights can be positive, negative, or zero.

    This implementation uses a topological-sort based algorithm. The constructor takes time proportional to V + E, 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.

    • 构造器概要

      构造器 
      构造器 说明
      AcyclicSP​(EdgeWeightedDigraph G, int s)
      Computes a shortest paths tree from s to every other vertex in the directed acyclic graph G.

    • 方法概要

      修饰符和类型 方法 说明
      double distTo​(int v)
      Returns the length of a shortest path from the source vertex s to vertex v.
      boolean hasPathTo​(int v)
      Is there a path from the source vertex s to vertex v?
      static void main​(java.lang.String[] args)
      Unit tests the AcyclicSP data type.
      java.lang.Iterable<DirectedEdge> pathTo​(int v)
      Returns a shortest path from the source vertex s to vertex v.

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

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

    • 构造器详细资料

      • AcyclicSP

        public AcyclicSP​(EdgeWeightedDigraph G,
                 int s)
        Computes a shortest paths tree from s to every other vertex in the directed acyclic graph G.
        参数:
        G - the acyclic digraph
        s - the source vertex
        抛出:
        java.lang.IllegalArgumentException - if the digraph is not acyclic
        java.lang.IllegalArgumentException - unless 0 <= s < V

    • 方法详细资料

      • distTo

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

      • hasPathTo

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

      • pathTo

        public java.lang.Iterable<DirectedEdge> pathTo​(int v)
        Returns a shortest path from the source vertex s to vertex v.
        参数:
        v - the destination vertex
        返回:
        a shortest path from the source vertex s to vertex v as an iterable of edges, and null if no such path
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= v < V

      • main

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