SHORTEST PATH USING DIJIKSTRA’S ALGORITHM..

METHOD 1

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

void main()

{

int graph[15][15],s[15],pathestimate[15],mark[15];

int num_of_vertices,source,i,j,u,predecessor[15],dest;

int count=0;

int minimum(int a[],int m[],int k);

void printpath(int,int,int[]);

clrscr();

printf("\nenter the no.of vertices\n");

scanf("%d",&num_of_vertices);

if(num_of_vertices<=0)

{

printf("\nthis is meaningless\n");

exit(1);

}

printf("\nenter the adjacent matrix\n");

for(i=1;i<=num_of_vertices;i++)

{

printf("\nenter the elements of row %d\n",i);

for(j=1;j<=num_of_vertices;j++)

{

scanf("%d",&graph[i][j]);

}}

printf("\nenter the source vertex\n");

scanf("%d",&source);

for(j=1;j<=num_of_vertices;j++)

{

mark[j]=0;

pathestimate[j]=999;

predecessor[j]=0;

}

pathestimate[source]=0;

while(count<num_of_vertices)

{

u=minimum(pathestimate,mark,num_of_vertices);

s[++count]=u;

mark[u]=1;

for(i=1;i<=num_of_vertices;i++)

{

if(graph[u][i]>0)

{

if(mark[i]!=1)

{

if(pathestimate[i]>pathestimate[u]+graph[u][i])

{

pathestimate[i]=pathestimate[u]+graph[u][i];

predecessor[i]=u;

}}}}}

printf("\n possible path for source node having minimun cost:");

for(i=1;i<=num_of_vertices;i++)

{

printpath(source,i,predecessor);

if(pathestimate[i]!=999)

printf("is %d \n",pathestimate[i]);

}

printf("\n Enter the end node:");

scanf("%d",&dest);

printf("\n path of minimum cost for the source and dest:");

printpath(source,dest,predecessor);

printf("is %d \n",pathestimate[dest]);

getch();

}

int minimum(int a[],int m[],int k)

{

int mi=999;

int i,t;

for(i=1;i<=k;i++)

{

if(m[i]!=1)

{

if(mi>=a[i])

{

mi=a[i];

t=i;

}}}

return t;

}

void printpath(int x,int i,int p[])

{

printf("\n");

if(i==x)

{

printf("%d",x);

}

else if(p[i]==0)

printf("no path from %d to %d",x,i);

else

{

printpath(x,p[i],p);

printf("->%d",i);

}}

OUTPUT:

enter the no.of vertices

5

enter the adjacent matrix

enter the elements of row 1

0 6 15 8 1

enter the elements of row 2

6 0 7 10 11

enter the elements of row 3

15 7 0 1 1

enter the elements of row 4

8 10 1 0 9

enter the elements of row 5

1 11 1 9 0

enter the source vertex

2

 possible path for source node having minimun cost:

2->1 is 6

2 is 0

2->3 is 7

2->3->4 is 8

2->1->5 is 7

Enter the end node:5

Path of minimum cost for the source and dest:

2->1->5 is 7

METHOD 2

#include<stdio.h>

#include<conio.h>

#define INFINITY 999

    void read();

    void initialize();

    int getClosestUnmarkedNode();

    void dijkstra();

    void output();

    void printPath(int);

    int adjMatrix[15][15],predecessor[15],distance[15],mark[15],source,n,i,j;

void read()

{

  printf("\nEnter the number of vertices of the graph(should be > 0)\n");

  scanf("%d",&n);

    //Read the adjacency matrix for the graph with +ve weights

 printf("\nEnter the adjacency matrix for the graph\n");

 printf("\nTo enter infinity enter %d\n",INFINITY);

  for(i=1;i<=n;i++)

   {

    printf("\nEnter the (+ve)weights for the row %d ",i);

    for(j=1;j<=n;j++)

    scanf("%d",&adjMatrix[i][j]);

     }

  printf("\nEnter the source vertex\n");

  scanf("%d",&source);

}

void initialize()

{

  for(i=1;i<=n;i++) {

    mark[i] = 0;

    predecessor[i] = -1;

    distance[i] = INFINITY;

  }

  distance[source] = 0;

}

int getClosestUnmarkedNode()

{

  int minDistance = INFINITY;

  int closestUnmarkedNode;

  for(i=1;i<=n;i++)

   {

    if((!mark[i]) && ( minDistance >= distance[i]))

    {

                minDistance = distance[i];

                closestUnmarkedNode = i;

    }

   }

  return closestUnmarkedNode;

}

void dijkstra()

{

  int closestUnmarkedNode,count = 0;

  initialize();

  while(count < n)

  {

   closestUnmarkedNode = getClosestUnmarkedNode();

   mark[closestUnmarkedNode] = 1;

   for(i=1;i<=n;i++)

   {

   if((!mark[i]) && (adjMatrix[closestUnmarkedNode][i]>0) )

    {

    if(distance[i] >distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i])

        {

                        distance[i] = distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i];

                        predecessor[i] = closestUnmarkedNode;

         }

      }

    }

    count++;

  }

}

void printPath(int node)

{

  if(node == source)

    printf("%d...",node);

  else if(predecessor[node] == -1)

    printf("\nNo path from %d to %d \n",source,node);

  else

   {

    printPath(predecessor[node]);

    printf("%d...",node);

   }

}

void output()

 {

  for(i=1;i<=n;i++)

   {

    if(i == source)

     printf("%d ...%d",source,source);

    else

      printPath(i);

    printf("-> %d\n",distance[i]);

  }

}

void main()

{

  clrscr();

  printf("\nDijikstra's single source shortest path algorithm \n\n");

  read();

  dijkstra();

  output();

  getch();

}