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]