bellmanford算法求负环

Bellman-Ford算法可以用于检测图中是否存在负环。负环是指图中存在一个环，其权重之和为负数。下面是使用Bellman-Ford算法求解负环的步骤：

1. 初始化距离数组dist[]，将源节点的距离设置为0，其他节点的距离设置为正无穷大。

2. 对于图中的每条边(u, v, w)，按照边的顺序进行松弛操作。松弛操作即尝试通过边(u, v)缩短从源节点到节点v的路径长度。如果dist[u] + w < dist[v]，则更新dist[v]为dist[u] + w。

3. 重复执行步骤2，直到没有边可以进行松弛操作。

4. 再次遍历图中的每条边(u, v, w)，如果dist[u] + w < dist[v]，则存在负环。

如果Bellman-Ford算法执行了n-1轮松弛操作后，仍然存在可以进行松弛操作的边，则说明图中存在负环。这是因为在最短路径中，任何一个节点的最短路径长度最多经过n-1条边。

需要注意的是，Bellman-Ford算法的时间复杂度为O(V*E)，其中V是节点数，E是边数。