dag_longest_path#

dag_longest_path(G, weight='weight', default_weight=1, topo_order=None)[source]#

返回有向无环图（DAG）中的最长路径。

如果 G 的边带有 weight 属性，则使用边数据作为权重值。

参数:

GNetworkX DiGraph: 一个有向无环图 (DAG)
weightstr, 可选: 用于权重的边数据键
default_weightint, 可选: 没有权重属性的边的权重
topo_order: list 或 tuple, 可选: G 的拓扑序（如果为 None，函数将计算一个）

返回:

list: 最长路径

引发:

NetworkXNotImplemented: 如果 G 不是有向图

另请参阅

dag_longest_path_length

示例

>>> 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]

在存在多个有效拓扑序的情况下，可以使用 topo_order 指定一个特定的顺序

>>> 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]