algorithm - Bellman-ford算法是否始终可以检测加权图上的负圆？

这是我的代码：

#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

结果在我的电脑里：

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

但是，这个加权有向图有一个负圆。
我误解了负圆的概念。我说的话
上面是胡说八道此测试加权有向图不包含负圆。
我画了一幅画：
圆圈是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算法总能检测到负周期如果存在负循环（例如，当设置3～1到-100）时，该图不包含最短路径，因为您可以始终停留在循环中并获得更多负值。
参见例如Wikipedia。

关于algorithm - Bellman-ford算法是否始终可以检测加权图上的负圆？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30421179/