程序包 edu.princeton.cs.algs4

类 AcyclicLP

  • public class AcyclicLP
extends java.lang.Object
    The AcyclicLP class represents a data type for solving the single-source longest 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.

    • 构造器概要

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

    • 方法概要

      修饰符和类型 方法 说明
      double distTo​(int v)
      Returns the length of a longest 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 AcyclicLP data type.
      java.lang.Iterable<DirectedEdge> pathTo​(int v)
      Returns a longest path from the source vertex s to vertex v.

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

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

    • 构造器详细资料

      • AcyclicLP

        public AcyclicLP​(EdgeWeightedDigraph G,
                 int s)
        Computes a longest 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 longest path from the source vertex s to vertex v.
        参数:
        v - the destination vertex
        返回:
        the length of a longest path from the source vertex s to vertex v; Double.NEGATIVE_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 longest path from the source vertex s to vertex v.
        参数:
        v - the destination vertex
        返回:
        a longest 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 AcyclicLP data type.
        参数:
        args - the command-line arguments