shortest_path_length#

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

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

Parameters:
GNetworkX 图
source节点, 可选

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

target节点, 可选

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

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

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

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

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

Returns:
length: 数字或迭代器

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

如果仅指定了源，则返回一个以目标为键的字典，表示从源到该目标的最短路径长度。

如果仅指定了目标，则返回一个以源为键的字典，表示从该源到目标的最短路径长度。

如果源和目标都未指定，则返回一个迭代器，其中包含 (源, 字典)，字典以目标为键，表示从源到该目标的最短路径长度。

Raises:
NodeNotFound

如果 source 不在 G 中。

NetworkXNoPath

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

ValueError

如果 method 不是受支持的选项之一。

See also

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

Notes

路径的长度总是比路径中涉及的节点数少 1，因为长度测量的是所经过的边数。

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

Examples

>>> G = nx.path_graph(5)
>>> nx.shortest_path_length(G, source=0, target=4)
4
>>> p = nx.shortest_path_length(G, source=0)  # 未指定目标
>>> p[4]
4
>>> p = nx.shortest_path_length(G, target=4)  # 未指定源
>>> p[0]
4
>>> p = dict(nx.shortest_path_length(G))  # 未指定源和目标
>>> p[0][4]
4
On this page