shortest_path_length#

shortest_path_length(G, source=None, target=None, weight=None, method='dijkstra')[source]#

计算图中节点间的最短路径长度。

参数：
GNetworkX 图
source节点, 可选

路径的起始节点。如果未指定，则使用所有节点作为起始节点计算最短路径长度。

target节点, 可选

路径的结束节点。如果未指定，则使用所有节点作为结束节点计算最短路径长度。

weightNone, 字符串或函数, 可选 (默认为 None)

如果为 None，则每条边的权重/距离/成本为 1。如果为字符串，则使用此边属性作为边权重。任何不存在的边属性默认为 1。如果为函数，则边的权重是函数返回的值。该函数必须接受三个位置参数：边的两个端点以及该边的属性字典。该函数必须返回一个数字。

method字符串, 可选 (默认为 ‘dijkstra’)

计算路径长度所使用的算法。支持的选项有：‘dijkstra’，‘bellman-ford’。其他输入会产生 ValueError。如果 weight 为 None，则使用无权图方法，并忽略此建议。

返回：
length: 数字或迭代器

如果同时指定了 source 和 target，则返回从 source 到 target 的最短路径长度。

如果只指定了 source，则返回一个以 target 为键，值为从 source 到该 target 的最短路径长度的字典。

如果只指定了 target，则返回一个以 source 为键，值为从该 source 到 target 的最短路径长度的字典。

如果 source 和 target 都没有指定，则返回一个迭代器，迭代内容为 (source, dictionary)，其中 dictionary 以 target 为键，值为从 source 到该 target 的最短路径长度。

抛出：
NodeNotFound

如果 source 不在 G 中。

NetworkXNoPath

如果 source 和 target 之间不存在路径。

ValueError

如果 method 不在支持的选项中。

另请参阅

all_pairs_shortest_path_length
all_pairs_dijkstra_path_length
all_pairs_bellman_ford_path_length
single_source_shortest_path_length
single_source_dijkstra_path_length
single_source_bellman_ford_path_length

备注

路径的长度总是比路径中包含的节点数少 1，因为长度衡量的是边的数量。

对于有向图，这返回最短的有向路径长度。要查找反向的路径长度，首先使用 G.reverse(copy=False) 翻转边的方向。

示例

>>> G = nx.path_graph(5)
>>> nx.shortest_path_length(G, source=0, target=4)
4
>>> p = nx.shortest_path_length(G, source=0)  # target not specified
>>> p[4]
4
>>> p = nx.shortest_path_length(G, target=4)  # source not specified
>>> p[0]
4
>>> p = dict(nx.shortest_path_length(G))  # source,target not specified
>>> p[0][4]
4
----

其他后端实现了此函数

cugraphGPU 加速后端。

尚不支持负权重。

附加参数
dtypedtype 或 None, 可选

算法中用于边权重的数据类型 (np.float32, np.float64, 或 None)。如果为 None，则 dtype 由边值确定。

在本页