<p>你仍然可以用贝尔曼福特。在这里,我将<a href="https://cp-algorithms.com/graph/finding-negative-cycle-in-graph.html" rel="nofollow noreferrer">finding-negative-cycle-in-graph</a>中的代码改编为python,并添加了一个运行示例。在</p>
<pre><code>import matplotlib.pyplot as plt
import networkx as nx
import numpy as np
def getW(edge):
return edge[2]['weight']
def getNegativeCycle(g):
n = len(g.nodes())
edges = list(g.edges().data())
d = np.ones(n) * 10000
p = np.ones(n)*-1
x = -1
for i in range(n):
for e in edges:
if d[int(e[0])] + getW(e) < d[int(e[1])]:
d[int(e[1])] = d[int(e[0])] + getW(e)
p[int(e[1])] = int(e[0])
x = int(e[1])
if x == -1:
print("No negative cycle")
return None
for i in range(n):
x = p[int(x)]
cycle = []
v = x
while True:
cycle.append(str(int(v)))
if v == x and len(cycle) > 1:
break
v = p[int(v)]
return list(reversed(cycle))
G = nx.DiGraph()
G.add_edge('0', '1', weight=0.1)
G.add_edge('1', '2', weight=-1)
G.add_edge('2', '3', weight=-0.3)
G.add_edge('3', '0', weight=-0.4)
G.add_edge('4', '3', weight=0.7)
G.add_edge('4', '5', weight=0.9)
G.add_edge('3', '5', weight=-5)
cycle = getNegativeCycle(G)
</code></pre>
<p>这将输出一个负循环:</p>
^{pr2}$
<p><strong>注意</strong>为了简单起见(数组位置),我使用了编号顶点。在</p>