Dijkstra's Algorithm in C

Monday 8 October 2012
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..

Copyright @ 2013 code-craft. Designed by Templateism | MyBloggerLab