single_source_dijkstra_path

single_source_dijkstra_path(G, source, cutoff=None, weight='weight')

在图 G 中查找从源节点出发的最短加权路径。

计算加权图中源节点与所有其他可达节点之间的最短路径。

参数：

GNetworkX 图

source节点

路径的起始节点。

cutoff整数或浮点数，可选

搜索停止时的长度（边权重的总和）。如果提供了 cutoff，则只返回总权重 <= cutoff 的路径。

weight字符串或函数

如果这是字符串，则通过具有此键的边属性访问边权重（即，连接 u 和 v 的边的权重将是 G.edges[u, v][weight]）。如果不存在这样的边属性，则假定边权重为 1。

如果这是函数，则边的权重是该函数返回的值。该函数必须接受恰好三个位置参数：边的两个端点以及该边的边属性字典。该函数必须返回一个数字或 None 以表示隐藏的边。

返回：

paths字典

以目标为键的最短路径长度字典。

引发：

NodeNotFound

如果 source 不在 G 中。

另请参阅

single_source_dijkstra, single_source_bellman_ford

注意

边权重属性必须是数值。距离计算为遍历的加权边的总和。

可以通过返回 None 来使用权重函数隐藏边。因此，weight = lambda u, v, d: 1 if d['color']=="red" else None 将找到最短的红色路径。

示例

>>> G = nx.path_graph(5)
>>> path = nx.single_source_dijkstra_path(G, 0)
>>> path[4]
[0, 1, 2, 3, 4]
----

其他后端实现了此函数

cugraphGPU 加速后端。

附加参数

dtypedtype 或 None，可选

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