shortest_simple_paths#
- shortest_simple_paths(G, source, target, weight=None)[源代码]#
- 生成图G中从源到目标的所有简单路径,
从最短的开始。
简单路径是没有重复节点的路径。
如果要使用加权最短路径搜索,则不允许使用负权重。
- 参数
- G网络X图表
- source结点
路径的起始节点
- target结点
路径的结束节点
- weight字符串或函数
如果它是字符串,则它是要用作权重的边属性的名称。
如果是函数,则边的权重是函数返回的值。该函数必须精确地接受三个位置参数:边的两个端点和该边的边属性字典。函数必须返回一个数字。
如果没有,则所有边都被认为具有单位重量。默认值无。
- 返回
- 路径生成器:生成器
生成简单路径列表的生成器,按从最短到最长的顺序排列。
- 加薪
- NetworkXNoPath
如果在源和目标之间没有路径存在。
- NetworkXError
如果源或目标节点不在输入图中。
- NetworkXNotImplemented
如果输入图是多个 [Di] 图表。
参见
all_shortest_paths
shortest_path
all_simple_paths
笔记
本程序是基于金元元的算法 [1]. 寻找第一个 \(K\) 路径需要 \(O(KN^3)\) 运营部。
工具书类
- 1
金永元,“在网路中寻找K最短无环路径”,《管理科学》,第17卷,第11期,理论丛书(1971年7月),第712-716页。
实例
>>> G = nx.cycle_graph(7) >>> paths = list(nx.shortest_simple_paths(G, 0, 3)) >>> print(paths) [[0, 1, 2, 3], [0, 6, 5, 4, 3]]
您可以使用此函数有效地计算两个节点之间的k最短/最佳路径。
>>> from itertools import islice >>> def k_shortest_paths(G, source, target, k, weight=None): ... return list( ... islice(nx.shortest_simple_paths(G, source, target, weight=weight), k) ... ) >>> for path in k_shortest_paths(G, 0, 3, 2): ... print(path) [0, 1, 2, 3] [0, 6, 5, 4, 3]