shortest_simple_paths

shortest_simple_paths(G, source, target, weight=None)

生成图 G 中从源节点到目标节点的所有简单路径，

从最短路径开始。

简单路径是指没有重复节点的路径。

如果要使用加权最短路径搜索，不允许存在负权重。

参数:

GNetworkX 图

source节点

路径的起始节点

target节点

路径的结束节点

weight字符串或函数

如果是一个字符串，它将用作边的属性名称作为权重。

如果是一个函数，边的权重是函数返回的值。函数必须接受三个位置参数：边的两个端点和该边的属性字典。函数必须返回一个数字或 None。通过返回 None，权重函数可以用于隐藏边。例如，weight = lambda u, v, d: 1 if d['color']=="red" else None 将找到最短的红色路径。

如果为 None，则所有边都被认为具有单位权重。默认值为 None。

返回:

path_generator: 生成器

一个生成器，按从短到长的顺序生成简单路径列表。

抛出:

NetworkXNoPath

如果源节点和目标节点之间不存在路径。

NetworkXError

如果源节点或目标节点不在输入图中。

NetworkXNotImplemented

如果输入图是 Multi[Di]Graph。

另请参阅

all_shortest_paths (所有最短路径)

shortest_path (最短路径)

all_simple_paths (所有简单路径)

注意

此过程基于 Jin Y. Yen [1] 的算法。找到前 \(K\) 条路径需要 \(O(KN^3)\) 次操作。

参考文献

[1]

Jin Y. Yen, "Finding the K Shortest Loopless Paths in a Network", Management Science, Vol. 17, No. 11, Theory Series (Jul., 1971), pp. 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]