Dijkstra's algorithm(Shortest Path) C program

#include<stdio.h>
#include<string.h>
#define INFINITY 999
int DJ(int adj[][100], int src,int dst);
char path[100];
int n;
main()
{
    int adj[100][100],src,dst,i,j,wt,len;
    char ch;
    printf("\t\nShortest Route Path(DIJKSTRA's ALGORITHM)\n\n");
    printf("\n\nEnter The No. of Nodes : ");
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            adj[i][j]=INFINITY;
    for(i=1;i<=n;i++)
    {
        for(j=i+1;j<=n;j++)
        {
            fflush(stdin);
            printf("\n\nIs There Any Edge Present B/W The Nodes %d And %d (Y or N) : ",i,j);
            scanf("%c",&ch);
            if(ch=='y'||ch=='Y')
            {
                printf("\n\nEnter The Weight Of The Edge B/W The Nodes %d And %d: ",i,j);
                scanf("%d",&wt);
                adj[i][j]=adj[j][i]=wt;
            }
        }
    }
    while(1)
    {
        printf("\n\nEnter The Source : ");
        scanf("%d",&src);
        printf("\n\n\t\tShortest Route ");
        printf("\n\nFrom\tTo\tPath\t\t\tlength/cost");
        for(i=1;i<=n;i++)
        {
            if(i==src)
                continue;
            len=DJ(adj,src,i);
            printf("\n\n%d\t%d\t%s\t\t\t%d",src,i,path,len);
        }
        printf("\n\nDo You Want To Continue..(Y or N) : ");
        fflush(stdin);
        scanf("%c",&ch);
        if(ch=='n'||ch=='N')
            break;
    }
}
int DJ(int adj[][100],int src,int dst)
{
    int i,min,mi,current,d,dist[100],prev[100],visited[100]={0};

    for(i=1;i<=n;i++)
    {
        dist[i]=INFINITY;
        prev[i]=-1;
    }
    current=src;
    visited[current]=1;
    dist[current]=0;
    while(visited[dst]==0)
    {
        min=INFINITY;
        mi=0;
        for(i=1;i<=n;i++)
        {
            d=dist[current]+adj[current][i];
            if(d<dist[i]&&visited[i]==0)
            {
                dist[i]=d;
                prev[i]=current;
            }
            if(min>dist[i] && visited[i]==0)
            {
                min=dist[i];
                mi=i;
            }
        }
        current=mi;
        visited[current]=1;
    }
    current=dst;
    i=0;
    while(current!=-1)
    {
        path[i++]='-';
        path[i++]=current+48;
        path[i++]='-';
        current=prev[current];
    }
    path[i]='\0';
    strrev(path);
    return dist[dst];
}

SHARE

About Santhosh