Вот мой код:
#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
//Следующий код проверяет наличие отрицательного круга. символ я был повторен до 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
Такова ли природа Беллман-форда?
