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

Question

Here is my code:

#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;
}

And here is my test data:

1 2 2
0 1 -3
0 4 5
3 4 2
2 3 3
3 1 -3

And result in my computer:

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

But, this weighted digraph do have a negative circle.

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

And I draw a picture:

The circle is 1->2->3->1

But the program doesn't report it.

Analyse the last data:

3 1 -3

//The following code is testing if have negative circle. symbol i have been iterated to 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) is false !

So that's the problem ,

If I set the weight of 3->1 to -100, the algorithm can detect the negative circle.

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

count = 4

So Is this kind of nature of Bellman-ford?

Answer 1

Yes, the Bellman–Ford algorithm can always detect negative cycles. If a negative cycle exists (e.g. when you set 3->1 to -100), the graph contains no shortest path because you can always stay in the cycle and get more negative values.

See e.g. Wikipedia.