shortest_simple_paths

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

生成图 G 中从源到目标的所有简单路径，从最短路径开始。

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

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

Parameters:

GNetworkX 图

source节点

路径的起始节点

target节点

路径的结束节点

weight字符串或函数

如果是字符串，则是用作边权重的边属性的名称。

如果是函数，边的权重是函数返回的值。该函数必须接受三个位置参数：边的两个端点和该边的边属性字典。函数必须返回一个数字。

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

Returns:

path_generator: 生成器

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

Raises:

NetworkXNoPath

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

NetworkXError

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

NetworkXNotImplemented

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

See also

all_shortest_paths

shortest_path

all_simple_paths

Notes

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

References

[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.

Examples

>>> 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]