shortest_path#

shortest_path(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，则使用无权图方法，并且忽略此建议。

返回:
path: 列表或字典

所有返回的路径都包含源节点和目标节点。

如果同时指定了源节点和目标节点，则返回从源节点到目标节点的最短路径中的节点列表。

如果仅指定了源节点，则返回一个字典，其键是目标节点，值是从源节点到其中一个目标节点的最短路径中的节点列表。

如果仅指定了目标节点，则返回一个字典，其键是源节点，值是从其中一个源节点到目标节点的最短路径中的节点列表。

如果既未指定源节点也未指定目标节点，则返回一个字典的字典，其中 path[source][target]=[路径中的节点列表]。

引发:
NodeNotFound

如果 source 不在 G 中。

ValueError

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

另请参阅

all_pairs_shortest_path
all_pairs_dijkstra_path
all_pairs_bellman_ford_path
single_source_shortest_path
single_source_dijkstra_path
single_source_bellman_ford_path

注意

源节点和目标节点之间可能存在多条最短路径。此函数仅返回其中一条。

示例

>>> G = nx.path_graph(5)
>>> print(nx.shortest_path(G, source=0, target=4))
[0, 1, 2, 3, 4]
>>> p = nx.shortest_path(G, source=0)  # target not specified
>>> p[3]  # shortest path from source=0 to target=3
[0, 1, 2, 3]
>>> p = nx.shortest_path(G, target=4)  # source not specified
>>> p[1]  # shortest path from source=1 to target=4
[1, 2, 3, 4]
>>> p = dict(nx.shortest_path(G))  # source, target not specified
>>> p[2][4]  # shortest path from source=2 to target=4
[2, 3, 4]
----

其他后端实现了此函数

cugraphGPU 加速后端。

暂不支持负权重。

附加参数
dtypedtype 或 None，可选

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

在本页上