python - networkx 中具有要访问的“关键”节点的最短路径
问题描述
我在用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)))
推荐阅读
- python - 数据框的剂量元数据有助于为 ML 算法构建特征
- go - 运行 get vs build 时的 Go 模块
- javascript - 有没有办法使用 php 或 javascript 将视频转换为图像?
- vb.net - For Each 是否引用对象本身或它们的值?
- css - 边缘自定义滚动条
- typescript - 如何从打字稿中的浮点数中获取点之后的数字
- angular - 以角度将可观察对象用于 http 请求的最佳方法是什么?
- java - Java-8 中的方法引用和泛型
- powerbi - 如何将 Power BI 中的最大值和平均值与筛选器结合使用
- web-scraping - 我如何更改 Scrapy 以在洋葱链接上爬行?