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.

No comments:

Post a comment