Hello friends ...
See this code for Dijkastra Algorithm implemetation in C language....
sourcefile: DIJKSTRA.c
inputfile: topologyfile.txt
How to run In linux...
compiling file....
$gcc DIJKASTRA.c -o DJ
running file....
$gcc DJ topologyfile.txt
source code:DIJKASTRA.c/***************************************************************************/
#include <
stdio.h >
#include <
stdlib.h >
#define INFY 1000
int dist[50], Q[50], sdata[50], sQ[50], dist_between[50][50];
int k,N;
/*------------------------------------------------------------------------
* sortQ - function to sort the Q for getting the vertex with least dist[]
*------------------------------------------------------------------------
*/
void sortQ (int k)
{
int i,j,temp;
for( i = 0;i <
N-k; i++)
{
for( j = i+1;j <
N-k; j++)
{
if(sdata [i] >
sdata[j])
{
temp = sdata[j];
sdata[j] = sdata[i];
sdata[i] = temp;
temp = sQ[j];
sQ[j] = sQ[i];
sQ[i] = temp;
}
}
}
}
/*------------------------------------------------------------------------
* shortetPath - finding single source shortest path from given source.
*------------------------------------------------------------------------
*/
void shortestPath(int source)
{
const int size=N;
int previous[size],v;
int temp,least,i,j,u=size; /*u value is set to N that is no. of nodes this is neccessary*/
int alt,t,b;
int uindex[size],m,l,flag;
for(i = 0 ;i <
N ;i++)
uindex[i] = N;
for(v = 0;v <
N; v++)
{
dist[v] = INFY;
previous[v] = -1;
Q[v] = v;
}
dist[source] = 0;
k = 0; /*while Q is not empty....*/
while(k <
N)
{
m = 0;
for(j = 0;j <
N; j++)
{
flag = 0; /*scan j value in uindex array if it is there dont put in sdata array*/
for(l = 0;l <
N; l++)
{
if(uindex[l] == j)
{
flag = 1;
break;
}
}
if(flag == 0)
{
sdata[m] = dist[j];
sQ[m] = j;
m++;
}
}
sortQ(k);
u = sQ[0];
uindex[k] = u;
k++;
for(i = 0;i <
N; i++)
{
if(dist_between[source][i] != 1000 || dist_between[source][i] != 0) /* Not infinity and not self node*/
{
if(dist[u]+dist_between[u][i] <
dist[i])
{
dist[i] = dist[u]+dist_between[u][i];
previous[i] = u;
}
}
}
}
printf("S----- >
D Dst Prnt");
for( i = 0;i <
N; i++)
{
b = previous[i];
printf("\n%d----- >
%d %d %d ",source ,Q[i] ,dist[i] ,Q[i]);
for(t = 0;t <
N; t++)
{
if(b != -1)
{
printf(" <
-----%d",b);
b = previous[b];
}
}
}
printf("\n");
}
/*------------------------------------------------------------------------
* main - Getting input and output files from user
*------------------------------------------------------------------------
*/
int main(int argc, char * argv[])
{
int i=0,j=0,v1,v2,delay,speed,in;
char *topofile,*connfile,*routefile,*forwardfile,*pathfile;
FILE *tf=NULL,*cf=NULL,*rf=NULL,*ff=NULL,*pf=NULL;
topofile=argv[1];
printf("%s\n",topofile);
/*connfile=argv[2];
routefile=argv[3];
forwardfile=argv[4];
pathfile=argv[5];*/
tf=fopen(topofile,"r");
fscanf(tf,"%d",&N);
const int size=N;
for(i=0;i <
N;i++)
{
for(j=0;j <
N;j++)
{
if(i!=j)
dist_between[i][j]=INFY;
else
dist_between[i][j]=0;
}
}
while(!feof(tf))
{
fscanf(tf,"%d",&v1);
fscanf(tf,"%d",&v2);
fscanf(tf,"%d",&delay);
fscanf(tf,"%d",&speed);
dist_between[v1][v2]=delay;
dist_between[v2][v1]=delay; /*As the link is bidirectional*/
i++;
}
for(in=0;in <
N;in++)
{
shortestPath(in);
printf("\n-------------------------------------------\n");
}
return 0;
}
/******************************************************************************/
topologyfile.txt7
0 1 6 1
0 2 5 1
0 3 5 1
1 4 4 1
2 4 3 1
1 2 2 1
2 3 2 1
3 5 2 1
4 6 3 1
5 6 3 1
you can change the topology file as a input of new topology...
and this program does not uses Queue structure....
for deleting least dist[] value node...
so not complicated....
