Scribd
Upload
74 views

Code Dijkstra's Algorithm

Algorithm of Dijkstra for optimization for calculating the shortest path in the given network. The code is for 6 nodes network only

Uploaded by

tchoudhariyahoocom
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
74 views

Code Dijkstra's Algorithm

Algorithm of Dijkstra for optimization for calculating the shortest path in the given network. The code is for 6 nodes network only

Uploaded by

tchoudhariyahoocom
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 5

CE 744 Analysis of Transportation Systems

Assignment
Dijkstras Algorithm in C language

Submitted by
TUSHAR CHOUDHARI (143040009)
GAJANAN VAIRAGAD (143040012)

DATE
25/09/2014

CODE:
#include<stdio.h>
#include<conio.h>
#define INFINITY 2000
#define MAXNODES 6
#define MEMBER 1
#define NONMEMBER 0
void shortpath(int weight[][MAXNODES], int , int ,int * ,int precede[]);
int main(void)
{
int i,j,s,t;
int weight[MAXNODES][MAXNODES],precede[MAXNODES],pd;

printf("For this program, input file should be given by the notepad file for ease in \nwriting the
weight/cost values, with name 'input' and to be saved in the folder where program file is saved.\n
Also show infinity value as 2000 in the input file.\n");
printf("\nThis program will work for 6 nodes only \nIf you want to change the no. of nodes, just
make fourth line of program as \n '#define MAXNODES N', \n where 'N' is no. of nodes to be
inserted \n");
//Inserting cost matrix
FILE *ip;
ip=fopen("input.txt","r");
if(ip==NULL)
{
printf("Input file not found, please copy input file in the folder \nwhere '.c' file is
saved\n");
exit (0);
}
else{printf("\nInput file found\n");}

printf("\nThe given cost/weight matrix is: \n");

for(i=0;i<MAXNODES;i++)
for(j=0;j<MAXNODES;j++)
2

{
fscanf(ip,"%d",&weight[i][j]);
}

printf("\n\n");
for(i=0;i<MAXNODES;i++)
{

for(j=0;j<MAXNODES;j++)
printf("%d\t",weight[i][j]);
printf("\n");

printf("\nConsider the starting node and the ending node: 1 and %d",MAXNODES);
s=0;
t=MAXNODES-1;

shortpath(weight,s,t,&pd,precede);
s++;t++;
printf("\n\nThe shortest path from node %d to %d is : %d\n\n",s,t,pd);
return(0);
}
void shortpath(int weight[][MAXNODES],int s, int t, int *pd, int precede[])
{
int distance[MAXNODES],perm[MAXNODES];
int current,i,j,k,dc;
int smalldist,newdist;
/* initialization of perm and distance array */
for(i=0;i<MAXNODES;i++)
{
perm[i]=NONMEMBER;
distance[i]=INFINITY;
}
perm[s] = MEMBER;
3

distance[s] = 0;
current = s;
while(current != t)
{
smalldist=INFINITY;
dc=distance[current];
for(i=0;i<MAXNODES;i++)
if(perm[i]==NONMEMBER)
{
newdist = dc + weight[current][i];
if(newdist < distance[i])
{
distance[i]=newdist;
precede[i]=current;
}
if(distance[i] < smalldist)
{
smalldist = distance[i];
k=i;
}
} /* end of for if */
current = k;
perm[current]=MEMBER;
} /* END WHILE */
*pd=distance[t];
}

/* end of shortpath function */

/* END OF PROGRAM */

OUTPUT:
For this program, input file should be given by the notepad file for ease in
writing the weight/cost values, with name 'input' and to be saved in the folder
where program file is saved.
Also show infinity value as 2000 in the input file.
4

This program will work for 6 nodes only


If you want to change the no. of nodes, just make fourth line of program as
'#define MAXNODES N',
where 'N' is no. of nodes to be inserted

Input file found

The given cost/weight matrix is:

2000 2000 2000

2000

2000 2000

2000

2000 0

2000

2000 2000 0

2000 7

2000

2000 2000 1

2000

2000 2000 2000 2000 2000

2000

Consider the starting node and the ending node: 1 and 6

The shortest path from node 1 to 6 is : 9


Press any key to continue . . .

You might also like