Shortest Path DCN

This program is for Finding Shortest Path. This is a part of Mumbai University MCA Colleges Data Communication and Networking MCA Sem 4

#include<stdio.h>

#include<conio.h>

#define size 100

int mat[size][size],v[size],nt[size],wt[size],t;

int newmat[size][size];

char ch[size][2];

int src,dest;

void print(int arr[size][size])

{

            int i,j;

            printf("%s\t"," ");

            for(i=0;i<t;i++)

                        printf("%s\t",ch[i]);

            printf("\n");

            for(i=0;i<t;i++)

            {

                        printf("%s\t",ch[i]);

                        for(j=0;j<t;j++)

                                    printf("%d\t",arr[i][j]);

                        printf("\n");

            }

}

void sink(int node)

{

            int i,j;

            v[node]=1;

            if(all_visit())

                        return;

            else

            {

                        for(i=0;i<t;i++)

                        {

//                                  print(newmat);

//                                  for(j=0;j<t;j++)

//                                              printf("(%s %s %d)\n",ch[j],ch[nt[j]],wt[j]);

//                                  getch();

                                    if(v[i]==0&&mat[node][i])

                                    {

                                                nt[i]=node;

                                                wt[i]=wt[node]+mat[node][i];

                                                newmat[node][i]=wt[i];

                                                newmat[i][node]=wt[i];

                                                sink(i);

                                    }

                                    else

                                    {

                                                if(v[i]==1&&mat[node][i]&&(wt[node]+mat[node][i])<wt[i])

                                                {

                                                            newmat[i][nt[i]]=0;

                                                            newmat[nt[i]][i]=0;

                                                            nt[i]=node;

                                                            wt[i]=wt[node]+mat[node][i];

                                                            newmat[node][i]=wt[i];

                                                            newmat[i][node]=wt[i];

                                                }

                                    }

                        }

            }

}

void clear()

{

            int i,j;

            for(i=0;i<t;i++)

            {

                        for(j=0;j<t;j++)

                        {

                                    mat[i][j]=0;

                                    newmat[i][j]=0;

                        }

                        v[i]=0;

                        wt[i]=0;

                        nt[i]=(i==src)?0:-1;

            }

}

int all_visit()

{

            int i;

            for(i=0;i<t;i++)

                        if(v[i]==0)

                                    return 0;

            return 1;

}

void main()

{

            int i,j,s,sel;

            clrscr();

            printf("\nEnter the Total Number of Node.\n");

            scanf("%d",&t);

            for(i=0;i<t;i++)

                        scanf("%s",&ch[i]);

            clear();

            for(i=0;i<t;i++)

            {

                        do

                        {

                                    printf("\nEnter the total Link for the Node %s:\n",ch[i]);

                                    scanf("%d",&s);

                        }while(!(s>=0&&s<=t));

                        for(j=0;j<s;j++)

                        {

                                    printf("\nEnter the node number\n");

                                    scanf("%d",&sel);

                                    printf("\nEnter the Weight.\n");

                                    scanf("%d",&mat[i][sel]);

                                    mat[sel][i]=mat[i][sel];

                        }

            }

            printf("\nThe Original Tree\n");

            print(mat);

            printf("\n\nEnter the nodes for which you want to find the shortest path:\t");

            scanf("%d",&src);

            printf("\nEnter the destination:\t");

            scanf("%d",&dest);

            sink(src);

            printf("\nShortest Path is %d\n",wt[dest]);

            print(newmat);

            for(i=0;i<t;i++)

                        printf("(%s %s %d)",ch[i],ch[nt[i]],wt[i]);

            getch();

}

Hope this Program is useful to you in some sense or other. Keep on following this blog for more Mumbai University MCA College Programs. Happy Programming and Studying.