Thursday , December 8 2016
Home / C / Programming on your Tips: program for dijkstra algorithm in c

Programming on your Tips: program for dijkstra algorithm in c

This is the program for dijkstra algorithm written in C. Dijkstra algorithm is the shortest path algorithm by which we can calculate distance of every node in a graph from a single source. 
#define IN 99

int dist[10],path[10];

int extract_min(int Q[], int n)

{

int i,temp[10],t=0,pos;

for(i=0;i

{

if(Q[i]!=-1)

temp[i]=1;

else

temp[i]=0;

}

for(i=0;i
{

if(t==0 && temp[i]==1)

{pos =i;

t=1;

continue;

}

if(temp[i]==1)

if(dist[i]
pos=i;

}

return pos;

}

int isempty(int Q[], int n)

{

int i;

for(i=0;i
{

if(Q[i]!=-1)

return 0;

}

return 1;

}

void initialize(int n,int s)

{

int i;

for(i=0;i
{

dist[i]=IN;

path[i]=-1;

}

dist[s]=0;

}

//Module which implement dijkstra algorithm
void dijkstra(int edge[10][10],int n,int s)

{

int Q[10],i,u,v,alt;

//Initialization step
initialize(n,s);

for(i=0;i
Q[i]=i+1;

while(isempty(Q,n)==0)

{

u=extract_min(Q,n);

Q[u]=-1;

if(dist[u]==IN)

break;

//Relax step
for(i=0;i
{

if(edge[u][i]!=0 && edge[u][i]!=IN)

{

v=i;

alt=dist[u]+edge[u][i];

if(alt
{

dist[v]=alt;

path[v]=u+1;

}

}

}

}

}

void main()

{

int n,edge[10][10],i,j,s,t;

clrscr();

printf(“Enter total number of vertices”);

scanf(“%d”,&n);

printf(“\nEnter Edge matrix in row major order”);

printf(“:  Enter 99 for Infinity and 0 for same vertices\n”);

for(i=0;i
{

for(j=0;j
scanf(“%d”,&edge[i][j]);

}

printf(“\n”);

printf(“Enter the source for finding shortest path: “);

scanf(“%d”,&s);

dijkstra(edge,n,s-1);

for(i=0;i
{

if(s-1==i)

continue;

if(dist[i]==IN)

{

printf(“PATH from %d to %d not exist\n”,i+1,s);

}

else

{

printf(“PATH from %d to %d is %d:”,i+1,s,i+1);

t=i;

for(j=1;j
{

printf(“<--%d",path[t]);

if(path[t]==s)

break;

t=path[t]-1;

}

printf(“\t DISTANCE : %d\n”,dist[i]);

} }

getch();

}

OUTPUT


Also See:   C program to Calculate Sum of Digits of a Number

Check Also

Hide Mouse Pointer C Program

How to Hide a Mouse Pointer Program in C : This program will show and hide ...

One comment

  1. some of the loops code is missing and one if condition code is missing

Leave a Reply

Your email address will not be published. Required fields are marked *

Preventing spam * Time limit is exhausted. Please reload the CAPTCHA.