find_negative_cycle#

find_negative_cycle(G, source, weight='weight')[source]#

返回一个包含负总权重的环，如果存在的话。

使用Bellman-Ford算法来寻找最短路径。该算法在存在负环时会停止。本算法从那里继续，并返回找到的负环。

环由环顺序中的一系列节点组成。最后一个节点等于第一个节点，以形成一个环。 你可以在原始图中查找边的权重。在多重图的情况下，相关的边是2-tuple中节点之间的最小权重边。

如果图中没有负环，则引发NetworkXError。

Parameters:
GNetworkX图
source: 节点标签

负环搜索将从该节点开始。

weight字符串或函数

如果是字符串，则通过该键访问边属性来获取边权重（即，连接 u 到 v 的边的权重将是 G.edges[u, v][weight] ）。如果不存在这样的边属性，则假设边的权重为1。

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

Returns:
cycle列表

按找到的环顺序排列的节点列表。最后一个节点等于第一个节点，以指示一个环。

Raises:
NetworkXError

如果没有找到负环。

Examples

>>> G = nx.DiGraph()
>>> G.add_weighted_edges_from(
...     [(0, 1, 2), (1, 2, 2), (2, 0, 1), (1, 4, 2), (4, 0, -5)]
... )
>>> nx.find_negative_cycle(G, 0)
[4, 0, 1, 4]
On this page