据说，“如果从源可以到达负边缘循环，那么算法将返回错误”。
这个“从源头可达”是什么意思？
看下图：
你能给我一些例子，如果存在从源可以到达的负边缘循环，这个算法将返回 false。
注意：我是算法新手。
问问题
1808 次
2 回答
1
When the algorithm is used to find shortest paths, the existence of negative cycles is a problem, preventing the algorithm from finding a correct answer. However, since it terminates upon finding a negative cycle, the Bellman-Ford algorithm can be used for applications in which this is the target to be sought - for example in cycle-cancelling techniques in network flow analysis.
Please refer this link:- http://evlm.stuba.sk/~partner2/DBfiles/Optimization/Dynamical%20optimization/Optimization_EN_Ford-Belman_algorithm.pdf
于 2012-10-23T19:11:19.487 回答
1
这意味着如果存在一个总权重为负的循环，那么该算法无法给出答案，因为重复遵循该循环会“减少”路径的权重。我在您显示的图表中没有看到任何负重量周期（通过检查），因此在您的情况下，所述限制不应该成为问题。
编辑：“从源可达”意味着负权重循环只有在它是可达的情况下才是一个问题——这意味着存在从指定源到负权重循环中某个节点的路径——从起始节点或源节点。Bellman Ford 找到从一个显着节点到从该节点可到达的所有节点的最短路径。那有意义吗？
于 2012-10-23T19:08:23.127 回答