dag_longest_path#

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

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

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

Parameters:

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

Returns:

list: 最长路径

Raises:

NetworkXNotImplemented: 如果 G 不是有向的

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]

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

>>> DG = nx.DiGraph([(0, 1), (0, 2)])
>>> sorted(nx.all_topological_sorts(DG))  # 有效的拓扑排序
[[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]