Showing posts with label optimal path algorithm in C. Show all posts
Showing posts with label optimal path algorithm in C. Show all posts

Saturday, May 18, 2013

C Source Code for Dijkstra's Shortest Path Algorithm

Dijkstra's Shortest Path Algorithm is the popular algorithm for finding shortest/optimal path in compute science due to its widespread application in different branches- computer networks, distributed systems, signal processing etc.

I've implemented the algorithm for finding the minimum distance between any two nodes:



///......................................SHORTEST PATH ALGORITHM << Dijkstra Algorithm >>......................

#include<stdio.h>
#include<conio.h>
#define MAX_NODES 10
#define INFINITY 1000
#define MEMBER 1
#define NON_MEMBER 0

struct arc{
    int adj;
    int weight;
};
int main(){

    int i,j,k,weight[MAX_NODES][MAX_NODES],num_nodes,source,dest,precede[MAX_NODES];
    int distance[MAX_NODES],permanent_nodes_set[MAX_NODES];
    int current,current_distance,n;
    int smalldist,newdist;
    char s,d,node;

    printf("\n\t\t................................................................................\n");
    printf("\t\t\t\tSHORTEST PATH ALGORITHM << Dijkstra Algorithm >>");
    printf("\n\t\t................................................................................\n");
    printf("\n\n\t\t\tAssign 1000 as INFINITY for non-adjacent nodes !!\n\n");
    printf("\nEnter the number of nodes in the GRAPH :");
    scanf("%d",&n);

    for(i=0;i<n;i++)
        for(j=i+1;j<n;j++)
            {
                printf("\nEnter weight for arc[%c][%c] :",65+i,65+j);
                scanf("%d",&weight[i][j]);
                weight[j][i] =weight[i][j];
                weight[i][i] =INFINITY;
            }


    printf("\nEnter the source _node :");scanf(" %c",&s);
    source =(int)(s-97);
    printf("\nEnter the destination_node :");scanf(" %c",&d);
    dest = (int)(d-97);

    printf("\n\t\t\tThe shortest path is :>>\n\n\t\t\t");
    for(i=0;i<n;i++)
    {
        permanent_nodes_set[i] =NON_MEMBER;
        distance[i] =INFINITY;
    }
    permanent_nodes_set[source]=MEMBER;
    distance[source]=0;
    current=source;
    while(current!=dest)
    {
        smalldist =INFINITY;
        current_distance =distance[current];
        for(i=0;i<n;i++)
            if(permanent_nodes_set[i] ==NON_MEMBER)
        {
            newdist =current_distance+weight[current][i];
            if(newdist<distance[i])
            {
                distance[i]=newdist;
                precede[i]=current;
                if(node!=(65+current))
                    printf(" %c ->",65+current);
                node =65+current;

            }
            if(distance[i]<smalldist)
            {
                smalldist =distance[i];
                k =i;
            }

        }

         current =k;
         permanent_nodes_set[current] =MEMBER;

        }

        printf(" %c ->",65+dest);
        printf("\n\n\t\t\tThe shortest distance = %d\n",distance[dest]);

        getch();
        return 0;
}