擅长:python、mysql、java
<p>此代码不适用于未连接的图形
例如,对于以下情况,它给出了1,这是正确的:</p>
<pre><code>edges = []
edges.append([0, 1, 5])
edges.append([2, 3, -5])
edges.append([3, 4, -6])
edges.append([4, 2, -5])
edges.append([1, 2, 5])
print(bellmanFord(5, edges))
</code></pre>
<p>指向演示的链接:<a href="http://ideone.com/j8XAs3" rel="nofollow noreferrer">http://ideone.com/j8XAs3</a></p>
<p>当我们移除边1->;2时,它给出0,即使图有一个负循环(2->;3->;4->;2):</p>
^{pr2}$
<p>指向演示的链接:<a href="http://ideone.com/N4Bljk" rel="nofollow noreferrer">http://ideone.com/N4Bljk</a></p>
<hr/>
<p>编辑:</p>
<p>正如您所说的测试用例12在您使用每个顶点作为源之后通过的,我确实认为该图是不连通的,问题是解决方案的时间复杂性增加了现在是<code>O(n*n*m)</code>,即大约10^11个操作肯定会超时。在</p>
<p>因此,您可以按以下方式修改算法:</p>
<p>1)找到所有连接的组件,分离出该组件的顶点和边,并用这些顶点和边创建一个新的图</p>
<p>2)假设你现在有k个新的图形,对每一个都运行Bellman Ford。在</p>
<p>另外,你用“强连通”这个词是错误的,有向图是强连通的,如果从每个顶点到每个其他可能的顶点都有一条路径。在</p>
<p>我看到了你所指的问题,我假设它是“问题:检测货币汇率的异常”,如果我对这个问题是正确的,那么问题中给出的例子与它是强连接的事实相矛盾的,因为没有办法到达顶点4,但是图是连接的。在</p>
<p>问题中的示例:</p>
<pre><code>4 4
1 2 -5
4 1 2
2 3 2
3 1 1
</code></pre>
<p>如果这不是你所指的问题,或者你还有其他疑问,请告诉我。在</p>