networkx中具有“关键"节点要访问的最短路径 [英] Shortest Path in networkx with 'key' nodes to visit
本文介绍了networkx中具有“关键"节点要访问的最短路径的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我有一个用networkx开发的python G有向图.该图形的权重称为权重".
I have a directed graph in python G developed with networkx. The graph has weights called 'weight'.
我知道显式的起始节点A和结束节点F.在图之间可以访问节点B,C,D,E.
I know an explicit start node A and an End Node F. In between the graph can access the nodes B,C,D,E.
我该如何明确地说他必须通过找到最短路径来加入B和D,并且如果这有助于最短路径,则可以附加地添加C和E?
How can i explicity say that he has to acces B and D by finding the shortest path and can addionally add C and E, if this helps to the shortest path?
到目前为止,我知道该功能:
So far I know the function:
nx.single_source_dijkstra(G, 'A', target='F', cutoff=None, weight='weight')
给出输出:
(10.01,
['A',
'B',
'C',
'F',])
我如何确保它包含E?
推荐答案
Networkx没有针对您的问题的内置函数或参数.您应该手动执行此操作:
Networkx has no built-in functions or arguments for your problem. You should do it manually:
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)))
这篇关于networkx中具有“关键"节点要访问的最短路径的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文