Class ToposortDAGSolver<V>

    • Constructor Detail

      • ToposortDAGSolver

        public ToposortDAGSolver​(Graph<V> graph,
                                 V start)
        Constructs a new instance by executing the toposort-DAG-shortest-paths algorithm on the graph from the start.
        Parameters:
        graph - the input graph.
        start - the start vertex.
    • Method Detail

      • dfsPostOrder

        private void dfsPostOrder​(Graph<V> graph,
                                  V start,
                                  Set<V> visited,
                                  List<V> result)
        Recursively adds nodes from the graph to the result in DFS postorder from the start vertex.
        Parameters:
        graph - the input graph.
        start - the start vertex.
        visited - the set of visited vertices.
        result - the destination for adding nodes.
      • solution

        public List<V> solution​(V goal)
        Description copied from interface: ShortestPathSolver
        Returns the single-pair shortest path from a start vertex to the goal.
        Specified by:
        solution in interface ShortestPathSolver<V>
        Parameters:
        goal - the goal vertex.
        Returns:
        a list of vertices representing the shortest path.