Bellman-ford 算法是否总能检测到加权有向图中的负圆？

Question

这是我的代码：

#include<stdio.h>
#include<stdlib.h>

#define inf 99999999

#define vertex 5
#define edge 6

int main(){
    int dis[vertex]={
        0,inf,inf,inf,inf
    };
    int bak[vertex];
    int u[edge],v[edge],w[edge];
    int i,
        k,
        check = 0,
        flag = 0,
        count = 0;
    for(i = 0 ;i<edge;i++){
        scanf("%d %d %d\n",&u[i],&v[i],&w[i]);
    }

    // test if data is received correctly
    for(i = 0 ; i<edge;i++){
        printf("%d %d %d\n",u[i],v[i],w[i]);
    }
    //test_end

    for(k = 0 ;k<vertex-1;k++){   // relax at most vertex-1 time
        count ++;

        /* check = 0; */
        /* for(i = 0 ;i<vertex ;i++){ */
            /* bak[i] = dis[i]; */
        /* } */

        for(i = 0 ;i<edge;i++){
            if(dis[v[i]] > dis[u[i]] + w[i]){
                dis[v[i]] = dis[u[i]] + w[i];
            }
        }

        /* for(i = 0;i<vertex;i++){ */
            /* if(bak[i] != dis[i]){ */
                /* check = 1; */
                /* break; */
            /* } */
        /* } */
        /* if(check == 0){ */
            /* break; */
        /* } */
    }

    // test if have negative circle
    for(i = 0 ; i< edge ;i++){   
        if(dis[v[i]] > dis[u[i]] + w[i])
            flag = 1;
    }
    //test_end 

    if(flag == 1){
        printf("Have circle\n");
    }
    else{
        printf("No circle\n");

        for(i = 0 ; i< vertex;i++){
            printf("%d ",dis[i]);
        }
    }

    printf("\ncount = %d \n",count);

    return 0;
}

这是我的测试数据：

结果在我的电脑中：

1 2 2
0 1 -3
0 4 5
3 4 2
2 3 3
3 1 -3
No circle
0 -3 -1 2 4
count = 4

但是，这个加权有向图确实有负圆

I misunderstanding the conception of negative circle. What I said above was nonsense. This test weighted digraph contains no negative circle.

然后我画了一幅画：

圆是1->2->3->1

但是程序没有报告。

分析最后的数据：

3 1 -3

//下面的代码是测试是否有负圆。符号 i 已经迭代到 5

if(dis[v[i]] > dis[v[i]] + w[i]){
    flag = 1;
}

//dis[1] now is -3 ,
//dis[3] now is 2 ,
//w[5] is -3

-3 > 2 + (-3) 为假！

这就是问题所在，

如果我把3->1的权重设置为-100，算法就可以检测到负圆

1 2 2
0 1 -3
0 4 5
3 4 2
2 3 3
3 1 -100
Have circle

count = 4

那么Bellman-ford就是这种性格吗？

Answer 1

是的，Bellman–Ford 算法总能检测到负循环。如果存在负循环（例如，当您将 3->1 设置为 -100 时），则图形不包含最短路径，因为您始终可以留在循环中并获得更多个负值。

参见例如Wikipedia.

Answer 2

是的，毫无疑问，Bellman-ford 将以 100% 的准确度检测负循环。如果你的程序是 C++，你可以应用这个函数：

#include <vector>
#include <set>
#include <utility>
#include <cstring>

using namespace std;

//Declare Global Variable for Data passing
#define MAX_NODE 1010 // 1 Million
#define INFINITY 1000000 // 1 Million

typedef pair<pair<int,int>,int> P; // 1-->2, Cost:3, then pair(node:1 node:2,cost:3)
vector<P> edgeList;
set<int> nodeList; // List of all nodes. Set prevents duplication.

int outDist[MAX_NODE];
int outPre[MAX_NODE];

bool BellmanFord(int source){

    // Initialize outDist
    for(int i=0;i<MAX_NODE;i++){
        outDist[i] = INFINITY;
    }
    //Initialize outPre
    memset(outPre,-1,sizeof(outPre));
    vector<P>::iterator edgeListItrEnd;
    vector<P>::iterator edgeListItrStart;
    P tmpPair;

    //we assume source distance is zero.
    outDist[source] = 0;

    int i,totalNode,rightNode,weight,leftNode;
    bool isComplete;
    totalNode = nodeList.size();

    edgeListItrEnd = edgeList.end();

    // Go through node 1 to N-1
    for(i=1; i<totalNode;i++){
        edgeListItrStart = edgeList.begin();
        // Iterate over all Edges
        isComplete = true;
        while(edgeListItrStart<edgeListItrEnd){
            tmpPair = *edgeListItrStart;
            leftNode = tmpPair.first.first;
            rightNode = tmpPair.first.second;
            weight = tmpPair.second;

            if((outDist[leftNode] != INFINITY) && (outDist[leftNode] + weight < outDist[rightNode])){
                //cout<<outDist[leftNode]<<" + "<<weight<<" < "<<outDist[rightNode]<<endl;
                isComplete = false;
                outDist[rightNode] = outDist[leftNode] + weight;
                outPre[rightNode] = leftNode;
            }
            edgeListItrStart++;
        }

        if(isComplete) return true;
    }

    // Check for Negative cycle;
    // Iterate over all edges
    edgeListItrStart = edgeList.begin();
    while(edgeListItrStart<edgeListItrEnd){
        tmpPair = *edgeListItrStart;
        leftNode = tmpPair.first.first;
        rightNode = tmpPair.first.second;
        weight = tmpPair.second;
        if((outDist[leftNode] != INFINITY) && (outDist[leftNode] + weight < outDist[rightNode])){
            return false;
        }
        edgeListItrStart++;
    }

    return true;
}

您可以在此处查看用途：https://kt48.wordpress.com/2015/06/16/bellman-ford-algorithm-c-implementation/

Bellman-ford 算法是否总能检测到加权有向图中的负圆？

Does Bellman-ford algorithm always can detect the negative circle in weighted digraph or not?

algorithm

bellman-ford