Bellman-Ford算法检测到什么？负重或负周期？ [英] What does Bellman-Ford algorithm detects? Negative weight or negative cycle?

问题描述

如果我们给出一个图，现在我们要计算最短路径。现在，如果一个边具有负权重，但是在到达目的地时返回边缘的边缘有边缘，我的意思是如果没有循环，那么我们没有负循环。但是维基百科中的这里给出了从源代码再次运行的算法，因此它检测负边权重但不是负周期。我的问题是，如何确定一个负循环？

解决方案

负重量周期是一个周期，数。 Bellman-Ford算法以V-1步骤向图中的所有节点传播正确的距离估计，除非有负的权重循环。如果存在负重量循环，则可以无限期地放松其节点。因此，如在维基百科算法中看到的，在V-1步骤之后放松边缘的能力是测试负重量周期的存在。因此，Bellman-Ford算法测试负重量周期。

If we are given a graph, Now from source we are to calculate the shortest path. Now , If an edge has a negative weight , but there is edge to back-edge to get back to that edge while reaching the destination I mean if there is no cycle, then we don't have a negative cycle. But the here in Wikipedia the given algorithm which runs from source again thus it detects a negative edge weight but not a negative cycle. My Question is, How to determine a negative cycle?

解决方案

A negative weight cycle is a cycle with weights that sum to a negative number. The Bellman-Ford algorithm propagates correct distance estimates to all nodes in a graph in V-1 steps, unless there is a negative weight cycle. If there is a negative weight cycle, you can go on relaxing its nodes indefinitely. Therefore, the ability to relax an edge after V-1 steps is a test for the presence of a negative weight cycle, as seen in the Wikipedia algorithm. So the Bellman-Ford algorithm tests for negative weight cycles.

这篇关于Bellman-Ford算法检测到什么？负重或负周期？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！