DIJKSTRA’S ALGORITHM

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