affiliate marketing

Monday, 12 December 2011

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

No comments:

Post a Comment