DIJKSTRA’S ALGORITHM
Aim
To implement Dijkstra’s algorithm
to find the shortest path.
Algorithm
Step1: [Include all the header
files]
Step2: Call allSelected( )
Step3: Call Shortpath( )
Step4: Access the functions from
main
Step5: End
Algorithm For ALLSELECTED( )
Step1: Initialise i=0
Step2: Check whether i<max
Step3: Check whether Selected[i]=0
Return 0
Step4: Else Return 1
Step5: Return
Algorithm For SHORTPATH( )
Step1: Initialise i=0 , Check i<max
Distance[i]=INFINITE
Step2: Assign
selected[current].distance[0]=0,
Current=0
Step3: While(!allSelected(Selected))
Perform(Selected[i]= =0)
Current=k
Selected[current]=1
Print k
Coding:
#include<stdio.h>
#include<conio.h>
#define max 4
#define INFINITE 998
int allselected( int *selected)
{
int
i;
for(i=0;i<max;i++)
if(selected[i]==0)
return
0;
return
1;
}
void shortpath(int cost[][max],int
*preceed,int *distance)
{
int
selected[max]={0};
int
current=0,i,k,dc,smalldist,newdist;
for(i=0;i<max;i++)
distance[i]=INFINITE;
selected[current]=1;
distance[0]=0;
current=0;
while(!allselected(selected))
{
smalldist=INFINITE;
dc=distance[current];
for(i=0;i<max;i++)
{
if(selected[i]==0)
{
newdist=dc+cost[current][i];
if(newdist<distance[i])
{
distance[i]=newdist;
preceed[i]=current;
}
if(distance[i]<smalldist)
{
smalldist=distance[i];
k=i;
}
}
}
current=k;
selected[current]=1;
}
}
int main()
{
int cost[max][max]={{INFINITE,2,4,INFINITE},{2,INFINITE,1,5},{4,1,INFINITE,2},{INFINITE,5,2,INFINITE}};
int preceed[max]={0},i,distance[max];
clrscr();
shortpath(cost,preceed,distance);
for(i=0;i<max;i++)
{
printf("The
shortest path from 0 to %d is ",i);
printf("%d\n",distance[i]);
}
return
0;
getch();
}
Output:
The shortest path from 0 to 0 is 0
The shortest path from 0 to 1 is 2
The shortest path from 0 to 2 is 3
The shortest path from 0 to 3 is 5
No comments:
Post a Comment