DAA - Dijkstra Program

 

Write a Program to implement Dijkstra’s algorithm for the Single source shortest path problem

 

Algorithm:

//G be a graph

//Cost matrix [1:n,1:n] for the graph G

//S={set of vertices that path already generated}

//Let V be source vertex

//dist[j];1<=j<=n denotes distance between V and j

void main()

{

for i:=1 to n do

{

s[i]=false; // initialize s with n

dist[i]=cost[v,i]; //define distance

}

s[v]=true; //put v in s

dist[v]=0.0; //Distance between v and v is 0

for num:=2 to n-1 do

{

paths from v //choose u from among those vertices not in S such that dist[u]=min;

s[u]=true;

for(each w adjascent to u with s[w]=false)

if(dist[w]>dist[u]+cost[u,w])

then

dist[w]=dist[u]+cost[u,w]; //update the distance

}

}

 

SOURCE CODE :

#include<stdio.h>

#include<conio.h>

#define INFINITY 9999

#define MAX 10

 void dijkstra(int G[MAX][MAX],int n,int startnode);

 int main()

{

int G[MAX][MAX],i,j,n,u;

printf("Enter no. of vertices:");

scanf("%d",&n);

printf("\nEnter the adjacency matrix:\n");

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

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

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

printf("\nEnter the starting node:");

scanf("%d",&u);

dijkstra(G,n,u);

return 0;

}

 void dijkstra(int G[MAX][MAX],int n,int startnode)

{

 int cost[MAX][MAX],distance[MAX],pred[MAX];

int visited[MAX],count,mindistance,nextnode,i,j;

//pred[] stores the predecessor of each node

//count gives the number of nodes seen so far

//create the cost matrix

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

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

if(G[i][j]==0)

cost[i][j]=INFINITY;

else

cost[i][j]=G[i][j];

//initialize pred[],distance[] and visited[]

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

{

distance[i]=cost[startnode][i];

pred[i]=startnode;

visited[i]=0;

}

distance[startnode]=0;

visited[startnode]=1;

count=1;

while(count<n-1)

{

mindistance=INFINITY;

//nextnode gives the node at minimum distance

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

if(distance[i]<mindistance&&!visited[i])

{

mindistance=distance[i];

nextnode=i;

}

//check if a better path exists through nextnode

visited[nextnode]=1;

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

if(!visited[i])

if(mindistance+cost[nextnode][i]<distance[i])

{

distance[i]=mindistance+cost[nextnode][i];

pred[i]=nextnode;

}

count++;

}

 

//print the path and distance of each node

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

if(i!=startnode)

{

printf("\nDistance of node%d=%d",i,distance[i]);

printf("\nPath=%d",i);

j=i;

do

{

j=pred[j];

printf("<-%d",j);

}while(j!=startnode);

}

}