bellman ford algorithm

Bellman ford algorithm c program-algorithm design and analysis(daa)
 

header.h
int bellman(int **a,int v,int m);


Main.c
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#include"header.h"

int main(){
int **a,v,i,j,m=-1;
struct timeval tim;
double time_start,time_end,time1;
FILE *fp;
fp=fopen("input.txt","r");
fscanf(fp,"%d",&v);
printf("the number of vertex is %d\n",v);
a=(int **)calloc(v,sizeof(int *));

for(i=0;i<v;i++){
a[i]=(int *)calloc(v,sizeof(int));
}

for(i=0;i<v;i++){
    for(j=0;j<v;j++){
        fscanf(fp,"%d",&a[i][j]);
        }
    }

printf("the adjacency matrix is :\n");
for(i=0;i<v;i++){
    for(j=0;j<v;j++){
        printf("%d ",a[i][j]);
        }
printf("\n");
    }

printf("the graph is :\n");
for(i=0;i<v;i++){
    for(j=0;j<v;j++){
        if(a[i][j]!=0)
        printf("%d-->%d  weight:%d\n",i,j,a[i][j]);
        }
    }

gettimeofday(&tim,NULL);
time_start=(double)tim.tv_sec +(double)(tim.tv_usec/1000000.0);

bellman(a,v,m);

gettimeofday(&tim,NULL);
time_end=(double)tim.tv_sec +(double)(tim.tv_usec/1000000.0);
time1=time_end-time_start;
printf("Execution time taken is %1f\n",time1);
}




Bellman.c
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>

struct table{
int source;
int destination;
int weight;
};
struct table obj[100];


int bellman(int **a,int v,int m){

int *visited,*key,i,flag=0,u,j;
int s,t;
visited=(int *)calloc(v,sizeof(int));
key=(int *)calloc(v,sizeof(int));

for(i=0;i<v;i++){
    for(j=0;j<v;j++){
        if(a[i][j]>0){
        m++;
        obj[m].source=i;
        obj[m].destination=j;
        obj[m].weight=a[i][j];
        }       
}
}

for(i=0;i<v;i++){
key[i]=INT_MAX;
}

key[0]=0;


for(i=1;i<=v-1;i++){
    for(j=0;j<m;j++){
    s=obj[j].source;
    t=obj[j].destination;
   
    if(key[s]+a[s][t]<key[t]){
    key[t]=key[s]+a[s][t];
    }
    }
  }

for(i=1;i<=v-1;i++){
    for(j=0;j<m;j++){
    s=obj[j].source;
    t=obj[j].destination;
   
    if(key[s]+a[s][t]<key[t]){
    printf("the graph contains negative edges\n");
    exit(1);
    }
    }
  }
printf("\nthe final distance is :\n");
for(i=0;i<v;i++){

printf("0-->%d  weight:%d\n",i,key[i]);
}
}



input.txt
5
0 4 3 0 0
7 0 9 0 0
0 0 0 2 0
0 0 0 0 8
0 0 6 0 0
 

Related Posts