如何用NetworkX计算有向图中指定节点的最长路径？

我有一个NetworkX有向图（DiGraph），想要计算从任意可达节点到指定节点的最长路径。现有的nx.dag_longest_path_length这类函数没办法直接满足这个需求。

我设想了两种可能的解决方案：

• 方案1：使用带有target参数的nx.shortest_path_length，将权重取反，再通过循环遍历源节点找到最大值？
• 方案2：使用类似nx.dag_longest_path_length(G.subgraph(G.predecessors(target)))的方法？

我认为这两种方法都不够简洁，想询问是否有更优的实现方式；若需从二者中选择，应选哪种及原因。

示例代码：

G = nx.DiGraph()
G.add_edge(1, 3, w=3)
G.add_edge(2, 3, w=5)
G.add_edge(3, 4, w=1)
# 现在我希望实现类似如下功能：
longest_path_to_node(G, target=3, weight="w")  # 预期输出：5

最优实现方式 #

最简洁高效的方法是反转有向图的边方向，然后利用NetworkX内置的最长路径函数直接计算：

原来的“从任意节点到target的最长路径”，等价于“反转边后从target到任意节点的最长路径”。针对DAG（有向无环图，这是最长路径问题有意义的前提——带正权环的图不存在最长路径），可以用nx.single_source_dag_longest_path_length直接获取结果，无需额外遍历。

完整实现代码：

import networkx as nx

def longest_path_to_node(G, target, weight=None):
    # 反转图的所有边方向
    reversed_graph = G.reverse()
    # 获取反转图中从target出发到所有可达节点的最长路径长度
    path_lengths = nx.single_source_dag_longest_path_length(reversed_graph, target, weight=weight)
    # 返回最长路径长度，若target无可达节点（仅自身）则返回0
    return max(path_lengths.values(), default=0)

# 测试示例
G = nx.DiGraph()
G.add_edge(1, 3, w=3)
G.add_edge(2, 3, w=5)
G.add_edge(3, 4, w=1)
print(longest_path_to_node(G, target=3, weight="w"))  # 输出5

两种方案的对比分析 #

1. 方案1（取反权重用最短路径）

   • 可行性：这种方法是可行的，但效率较低——需要遍历所有可能的源节点，逐个计算最短路径（取反权重后等价于最长路径），再取最大值。当图的节点数量较多时，性能会明显下降。
   • 注意：如果图中存在环，这种方法可能失效（因为带正权环的图没有最长路径，取反后变成负权环，最短路径也不存在）。

2. 方案2（取target前驱子图计算最长路径）

   • 问题：这个方法完全不可行。G.predecessors(target)只能获取target的直接前驱节点，子图中不会包含那些通过多步路径到达target的节点（比如如果有节点4→2→3，子图里只会有2，无法计算4→2→3的路径长度），会漏掉绝大多数有效路径，结果完全错误。

所以如果必须从二者中选，只能选方案1，但远不如反转图的方法简洁高效。

内容的提问来源于stack exchange，提问作者user344577