algorithm - 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

结果在我的电脑中:

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 .