我有一个用networkx开发的python G有向图。该图具有称为“权重”的权重。
我知道一个显式的起始节点 A 和一个结束节点 F。在图之间可以访问节点 B、C、D、E。
我如何明确地说他必须通过找到最短路径来访问 B 和 D,并且还可以添加 C 和 E(如果这有助于最短路径)?
到目前为止我知道这个功能:
nx.single_source_dijkstra(G, 'A', target='F', cutoff=None, weight='weight')
给出输出:
(10.01,
['A',
'B',
'C',
'F',])
我怎样才能确保它包含E?
Networkx 没有内置函数或参数来解决您的问题。您应该手动执行此操作:
import networkx as nx
# Create a 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])
nx.is_directed_acyclic_graph(DAG)
for edge in G.edges:
G.edges[edge]['weight'] = 1
# Get the longest path (without weights) from node 1 to node 40
# with nodes 5, 10, 20, 30 inside
max([
(path, len(path))
for path in nx.all_simple_paths(DAG, 1, 40)
if all(n in path for n in (5, 10, 20, 30))
], key=lambda x: x[1])
# Get the longest path (with weights)
max([
path
for path in nx.all_simple_paths(DAG, 1, 40)
if all(n in path for n in (5, 10, 20, 30))
], key=lambda x: sum(G.edges[edge]['weight'] for edge in nx.utils.pairwise(x)))
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)