dijkstra algorithm

Implement the Dijkstra's algorithm

header.h
int findmin(int *key,int v,int *visited);
int dijkstra(int **a,int v);


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

int main(){
int **a,v,i,j;
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 weight 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);

dijkstra(a,v);

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);

return 0;
}



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

int dijkstra(int **a,int v){

int *visited,*key,i,*parent,flag=0,u,t;

visited=(int *)calloc(v,sizeof(int));
key=(int *)calloc(v,sizeof(int));
parent=(int *)calloc(v,sizeof(int));

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

key[0]=0;

while(1){
flag=0;
u=findmin(key,v,visited);
if(u==v)
break;
visited[u]=1;

for(i=0;i<v;i++){
if(a[u][i]>0 && visited[i]==0){

    if(key[u]+a[u][i]<key[i]){
        key[i]=key[u]+a[u][i];
        parent[i]=u;
        }
}
}
}

printf("\nthe final path and weight by vertex is :\n");
for(i=1;i<v;i++){
t=i;
while(t!=0){
printf("%d-->",t);
t=parent[t];
}
printf("0  weight:%d\n",key[i]);
}
}



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

int findmin(int *key,int v,int *visited){
int i,pos,min=INT_MAX,flag=0;

for(i=0;i<v;i++){

if(key[i]<min && visited[i]==0){
flag=1;
min=key[i];
pos=i;
}

}
if(flag!=0)
return pos;
else
return v;

}


input.txt
5
8
0 1 1
1 4 2
0 2 4
1 2 3
1 3 2
3 1 1
4 3 3
3 2 5
0 4
Copyright © C Program | Java | OpenGL Programming | Hadoop at Computaholics