时间戳

首页 > 解决方案 > 如何在贝尔曼福特算法中检测负循环？

c++ - 如何在贝尔曼福特算法中检测负循环？

问题描述

以下是我用于实现用于检测图中负循环的贝尔曼福特算法的函数：

    int d[V]; // V is number of vertices in the graph, d[V] is the distance of the vertices from the source vertex

    vector<tuple<int,int,int>> edges; // defines edges as (u,v,w), where u and v are vertices and w is the weight b/w u and v

    int u,v,w;
    bool negativecycle_BF(int x){

        // x is the source vertex
        for(int i=1;i<=V;i++) d[i] = INF;

        d[x] = 0;

        for(int i=1;i<=V-1;i++){
            for(auto e:edges){
                tie(u,v,w) = e;
                d[v] = min(d[v], d[u]+w);  
            }
        }
        for(auto e: edges){
            tie(u,v,w) = e;
            if(d[v]>d[u]+w)
                return true;
        }
        return false;
    }

无论我是否有负循环，我的代码都只返回 0。有人可以指出我做错了什么吗？

标签： c++algorithmdata-structuresbellman-ford

解决方案

您已经分配d[v]了min(d[v], d[u]+w)，然后您检查了其中一个(d[v]>d[u]+w)，这永远不会是真的。因此，您总是会得到cpp中的return false哪个。0

顺便说一句，for(auto e: edges){...}缩进是错误的，所以如果你更正了，这将有助于更容易理解代码。

推荐阅读