Skip to main content
`Ctrl`+`K`

# dag_longest_path

dag_longest_path(G, weight='weight', default_weight=1, topo_order=None)

  Returns the longest path in a directed acyclic graph (DAG).

  If `G` has edges with `weight` attribute the edge data are used as weight values.

  Parameters:
    G NetworkX DiGraph

      A directed acyclic graph (DAG)

    weight str, optional

      Edge data key to use for weight

    default_weight int, optional

      The weight of edges that do not have a weight attribute

    topo_order: list or tuple, optional

      A topological order for `G` (if None, the function will compute one)

  Returns:
    list

      Longest path

  Raises:
    NetworkXNotImplemented

      If `G` is not directed

  See also

  `dag_longest_path_length`

  Examples

      >>> DG = nx.DiGraph(
      ...     [(0, 1, {"cost": 1}), (1, 2, {"cost": 1}), (0, 2, {"cost": 42})]
      ... )
      >>> list(nx.all_simple_paths(DG, 0, 2))
      [[0, 1, 2], [0, 2]]
      >>> nx.dag_longest_path(DG)
      [0, 1, 2]
      >>> nx.dag_longest_path(DG, weight="cost")
      [0, 2]

  In the case where multiple valid topological orderings exist, `topo_order` can be used to specify a specific ordering:

      >>> DG = nx.DiGraph([(0, 1), (0, 2)])
      >>> sorted(nx.all_topological_sorts(DG))  # Valid topological orderings
      [[0, 1, 2], [0, 2, 1]]
      >>> nx.dag_longest_path(DG, topo_order=[0, 1, 2])
      [0, 1]
      >>> nx.dag_longest_path(DG, topo_order=[0, 2, 1])
      [0, 2]