计算 NetworkX 中两个节点之间最长路径

Question

我正在尝试使用Networkx制作甘特图。网络中的所有节点均为完成项目所需执行的“任务”。使用Networkx很容易计算出项目的总时间。但是，要制作甘特图，则需要每个节点的最新开始时间。

NetworkX包括一个函数(dag_longest_path_length)，但它计算的是整个网络中的最长路径。另一个函数(astar_path_length)可以获得源节点和目标节点之间的最短路径，但没有可用于提供最长路径或最新开始时间的函数。(如果一个节点有两个前置节点，则会选择最快的路线，但实际上还必须等待第二个节点才能开始。

我考虑了一种方案：评估前面连接的节点并选择最长路径。不太正式，我没有成功。

start_time=[]
time=0
DD=nx.DiGraph()
for i in range(df.shape[0]):
        DD.add_edge(str(df.at[i,'blockT'])+'_'+df.at[i,'Task'], str(df.at[i,'blockS'])+'_'+df.at[i,'Succ'], weight=df.at[i,'duration'])


fig, ax = plt.subplots()  
labels=[]  
for i in range(df.shape[0]):
        labels.append(str(df.at[i,'blockT'])+'_'+df.at[i,'Task'])
        print(nx.astar_path_length(DD, '0_START', str(df.at[i,'blockT'])+'_'+df.at[i,'Task'])  ) 

ax.broken_barh([(nx.astar_path_length(DD, '0_START', str(df.at[i,'blockT'])+'_'+df.at[i,'Task']), heuristic=None, weight='weight'),df.at[i,'duration'] )],(i-0.4,0.8), facecolors='blue' )

- Tijmen

---

这个视频讲的是无向图，所以你的问题在计算上是可行的，但我还是很喜欢它。 - Joel

Answer 1

这是我使用的一些代码。我认为它应该成为NetworkX的一部分，因为它经常出现在我的工作中。graph必须是一个DiGraph。 s是源节点，dist是按节点排序的具有加权距离到s的dict。

    def single_source_longest_dag_path_length(graph, s):
        assert(graph.in_degree(s) == 0)
        dist = dict.fromkeys(graph.nodes, -float('inf'))
        dist[s] = 0
        topo_order = nx.topological_sort(graph)
        for n in topo_order:
            for s in graph.successors(n):
                if dist[s] < dist[n] + graph.edges[n,s]['weight']:
                    dist[s] = dist[n] + graph.edges[n,s]['weight']
        return dist

- Harris

---

这是一个很棒的答案，比迭代所有简单路径要快得多。 - AlaskaJoslin

支持无权图和起点不在末尾节点的单源最长有向无环图路径长度计算函数。def single_source_longest_dag_path_length(graph, s): dist = dict.fromkeys(graph.nodes, -float('inf')) dist[s] = 0 topo_order = nx.topological_sort(graph) for n in topo_order: for s in graph.successors(n): if dist[s] < dist[n] + 1: dist[s] = dist[n] + 1 return dist - AlaskaJoslin

Answer 2

看起来你正在使用DAG。

你的问题比较罕见，因此在networkx中没有内置函数可用。你应该手动处理：

max(nx.all_simple_paths(DAG, source, target), key=lambda x: len(x))

这里是完整的测试代码：

import networkx as nx
import random
from itertools import groupby

# Create random DAG
G = nx.gnp_random_graph(50,0.3,directed=True)
DAG = nx.DiGraph([(u,v) for (u,v) in G.edges() if u<v])

# Get the longest path from node 1 to node 10
max(nx.all_simple_paths(DAG, 1, 10), key=lambda x: len(x))

- vurmux

---

谢谢您的评论！然而，这种方法没有考虑节点的权重，只考虑了节点数量。因此它不会给出最新的开始时间，而是最长的路径。 - Tijmen

然后您可以使用类似这样的内容： max([(path, sum(DAG.edges[pair]['weight'] for pair in list(nx.utils.pairwise(path)))) for path in nx.all_simple_paths(DAG, 1, 10)], key=lambda x: x[1]) - vurmux