bellman_ford_path

bellman_ford_path(G, source, target, weight='weight')

返回加权图 G 中从 source 到 target 的最短路径。

参数：

GNetworkX 图

source节点

起始节点

target节点

终止节点

weight字符串或函数 (默认为“weight”)

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

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

返回：

path列表

最短路径中的节点列表。

引发：

NodeNotFound

如果 source 不在 G 中。

NetworkXNoPath

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

另见

dijkstra_path, bellman_ford_path_length

注释

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

示例

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

其他后端实现了此函数

cugraphGPU加速后端。

目前尚不支持负权重环。如果存在负边权重，将引发 NotImplementedError。我们计划很快支持负边权重。此外，不支持可调用（callable）的 weight 参数。

附加参数

dtypedtype 或 None，可选

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

graphblas : 支持 OpenMP 的稀疏线性代数后端。