Here's a graph algorithm implementation of Dijkstra's Algorithm in C .. input preferences are mentioned in comments in the program....
###########################################################################
/*Dijkrtas algorithm in C*/
#define N 6 //the number of vertices
#include<stdio.h>
#define INFINITY 999
#define TRUE 1
#define FALSE 0
int allvisited(int visits[])//checks if all nodes are visited or not
{
int i,flag=1;
for(i=0;i<N;i++)
{
if(visits[i]!=1)
flag=0;
}
return flag;
}
int dijkstra(int graph[][N],int target,int source)
{
int visited[N],dist[N];
//source -1 in actual matrix ..check row for neighbours
//init
int i;
for(i=0;i<N;i++)
{
dist[i]=INFINITY;
visited[i]=-1;
}
int start=source;
while(!allvisited(visited))
{
//printf("--->start=%d\n",start);
visited[start]=1;
if(dist[start]==INFINITY)
{
dist[start]=0;
}
for(i=0;i<N;i++)
{
if(graph[start][i]!=INFINITY)//this is a neighbour of start
{
int d=dist[start]+graph[start][i];
if(d<dist[i])
dist[i]=d;
}
}
//checking
/*for(i=0;i<N;i++)
printf("%d ",dist[i]);
printf("\n");*/
//get the next node i.e. will be the minimum of tentative dist and unvisited
int min=INFINITY;
int pos=INFINITY;
for(i=0;i<N;i++)
{
if(visited[i]!=1)
{
if(dist[i]<min)
{
min=dist[i];
pos=i;
}
}
}
//if pos==NULL then over
if(pos==INFINITY)
break;
else
start=pos;
//printf("continue..\n");
}
return dist[target];
}
int main()
{
int graph[N][N];
int i,j;
printf("Enter the graph::\n");
for(i=0;i<N;i++)
for(j=0;j<N;j++)
scanf("%d",&graph[i][j]);
//taken input must be symmetric and for i=j should be 0 and for not connected should be infinity as defined
int src,tar;
printf("Enter the source and target::");
scanf("%d %d",&src,&tar);
int dis=dijkstra(graph,tar-1,src-1);
printf("min dist=%d",dis);
return 0;
}
##################################################################################
If anyone wants the python or Java version please mention it in the comments and i will post it..
###########################################################################
/*Dijkrtas algorithm in C*/
#define N 6 //the number of vertices
#include<stdio.h>
#define INFINITY 999
#define TRUE 1
#define FALSE 0
int allvisited(int visits[])//checks if all nodes are visited or not
{
int i,flag=1;
for(i=0;i<N;i++)
{
if(visits[i]!=1)
flag=0;
}
return flag;
}
int dijkstra(int graph[][N],int target,int source)
{
int visited[N],dist[N];
//source -1 in actual matrix ..check row for neighbours
//init
int i;
for(i=0;i<N;i++)
{
dist[i]=INFINITY;
visited[i]=-1;
}
int start=source;
while(!allvisited(visited))
{
//printf("--->start=%d\n",start);
visited[start]=1;
if(dist[start]==INFINITY)
{
dist[start]=0;
}
for(i=0;i<N;i++)
{
if(graph[start][i]!=INFINITY)//this is a neighbour of start
{
int d=dist[start]+graph[start][i];
if(d<dist[i])
dist[i]=d;
}
}
//checking
/*for(i=0;i<N;i++)
printf("%d ",dist[i]);
printf("\n");*/
//get the next node i.e. will be the minimum of tentative dist and unvisited
int min=INFINITY;
int pos=INFINITY;
for(i=0;i<N;i++)
{
if(visited[i]!=1)
{
if(dist[i]<min)
{
min=dist[i];
pos=i;
}
}
}
//if pos==NULL then over
if(pos==INFINITY)
break;
else
start=pos;
//printf("continue..\n");
}
return dist[target];
}
int main()
{
int graph[N][N];
int i,j;
printf("Enter the graph::\n");
for(i=0;i<N;i++)
for(j=0;j<N;j++)
scanf("%d",&graph[i][j]);
//taken input must be symmetric and for i=j should be 0 and for not connected should be infinity as defined
int src,tar;
printf("Enter the source and target::");
scanf("%d %d",&src,&tar);
int dis=dijkstra(graph,tar-1,src-1);
printf("min dist=%d",dis);
return 0;
}
##################################################################################
If anyone wants the python or Java version please mention it in the comments and i will post it..