Shortest Path Algorithm: Dijkstra

Aim  :- To find shortest path

#include <iostream.h>

#include <conio.h>

 class graph

 {

  public:

  char a;

  char b;

  int e;

 };

 class dijkstra

 {

  public:

  int n,p,t,f;

  char c[10];

  void get_data();

  void get_connection(graph g[]);

  void shortest(graph g[]);

  void display(graph g[]);

  int minm(int [],int,char []);

  int findu(graph g[],int,int,char []);

 };

 void dijkstra::get_data()

 {

  cout<<"Enter number of nodes in your network:";

  cin>>n;

  cout<<endl<<"Write the name of each node"<<endl;

  for(int i=0;i<n;i++)

  {

   cout<<"Name of node "<<i+1<<":";

   cin>>c[i];

  }

 }

 void dijkstra::get_connection(graph g[])

 {

  clrscr();

  cout<<endl<<endl<<"NOW ITS TIME TO CONNECT THE NODES...!";

  cout<<endl<<"Enter 1 if there is connection between consicutive nodes otherwise enter 0"<<endl;

  p=0;

  for(int i=0;i<n;i++)

  {

   for(int j=i+1;j<n;j++)

   {

                cout<<c[i]<<" & "<<c[j]<<" :";

                int t;

                cin>>t;

                if(t==1)

                {

                 g[p].a=c[i];

                 g[p].b=c[j];

                 cout<<"Enter distance:";

                 cin>>g[p].e;

                 p++;

                }

   }

  }

 }

 void dijkstra::display(graph g[])

 {

  clrscr();

  cout<<"YOUR NETWORK IS LIKE THIS:"<<endl;

  for(int i=0;i<p;i++)

  {

   cout<<g[i].a<<" & "<<g[i].b<<" :"<<g[i].e<<endl;

  }

 }

 void dijkstra::shortest(graph g[])

 {

  char s,C[10];

  int q,D[10];

  cout<<endl<<endl<<"NOW ENTER NODE from which you want to find shortest distance:";

  cin>>s;

   t=0;

   f=0;

                //function to get distance & node array (Initialization)

  for(int r=0;r<n;r++)

  {

   if(s!=c[r])

   {

                C[f]=c[r];

                for(int i=0;i<p;i++)

                {

                 if((g[i].a==s && g[i].b==C[f]) || (g[i].a==C[f] && g[i].b==s))

                 {

                 D[f]=g[i].e;

                 q=0;

                 break;

                 }

                }

                if(q!=0)

                {

                D[f]=32767;

                }

                f++;

   }

  } int w,u,v;

  //greedy loop

  for(q=0;q<n-2;q++)

  {

   v=minm(D,f,C);

   for(w=0;w<f;w++)

   {

                if(C[w]!=NULL && C[w]!=C[v])

                {

                u=findu(g,w,v,C);

                D[w]=(D[w]<(u+D[v])?D[w]:(u+D[v]));

                }

   }

   C[v]=NULL;

  }

  cout<<"The sortest distance from node "<<s<<":";

  for(int z=0;z<f-1;z++)

  {

   cout<<D[z]<<",";

  }

   cout<<D[f-1];

 }

 int dijkstra::findu(graph g[],int w,int v,char C[])

 {

  for(int z=0;z<p;z++)

  {

   if((g[z].a==C[w] && g[z].b==C[v]) ||(g[z].a==C[v] && g[z].b==C[w]))

   {

                return g[z].e;

   }

  }

  return 32676;

 }

 int dijkstra::minm(int j[],int t,char c[])

 {

  int o=32766,q;

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

  {

   if(o>j[i] && c[i]!=NULL)

   {

                o=j[i];

                q=i;

   }

  }

  return q;

 }

 void main ()

 {

  clrscr();

  graph g[15];

  dijkstra d;

  d.get_data();

  d.get_connection(g);

  d.display(g);

  d.shortest(g);

  getch();

 }

Output:

Decimal To Binary Converter

//This Is The Program To Convert Decimal To Binary But Its Different From Other Ones!
#include<stdio.h>
void printBinary(int n);
void main()
{
int num;
printf("Enter Decimal Number\n");
scanf("%d",&num);
printBinary(num);
}
void printBinary(int n)
{
if (n>0)
{
printBinary(n/2);
printf("%c","01"[n%2]);
}
}

Synchronous TDM and Asynchronous TDM

// This is  Synchronous TDM developed using C

#include<stdio.h>

#include<string.h>

int main()

{

int i,j,k=0,l,maxlength=0,length[3],flag1=0,flag2=0,flag3=0;

char usr1[10],usr2[10],usr3[10],newusr1[10],newusr2[10],newusr3[10],b[100];

printf("enter data for user 1\n");

gets(usr1);

printf("enter data for user 2\n");

gets(usr2);

printf("enter data for user 3\n");

gets(usr3);

length[0]=strlen(usr1);

length[1]=strlen(usr2);

length[2]=strlen(usr3);

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

{

if(maxlength<length[j])

maxlength=length[j];

}

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

{

if(usr1[i]!=NULL && flag1==0)

b[k++]=usr1[i];

else

{

b[k++]='$';

flag1=1;

}

if(usr2[i]!=NULL && flag2==0)

b[k++]=usr2[i];

else

{

b[k++]='$';

flag2=1;

}

if(usr3[i]!=NULL && flag3==0)

b[k++]=usr3[i];

else

{

b[k++]='$';

flag3=1;

}

}

b[k]=NULL;

k=0;

for(i=1;i<=maxlength;i++)

{

printf("\nframe %d is ",i);

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

printf("%c",b[k++]);

}

strcpy(newusr1,usr3);

strcpy(newusr2,usr1);

strcpy(newusr3,usr2);

printf("\nTransferring Data To Respective Users...\n\n");

printf("user1 gets %s \n",newusr1);

printf("user2 gets %s \n",newusr2);

printf("user3 gets %s \n",newusr3);

return 0;

}

//This is  Asynchronous TDM developed using C

#include<stdio.h>
#include<ctype.h>
#include<string.h>
int main()
{
int i,j,k=0,l,frame,maxlength=0,length_t=0,length[3],flag1=0,flag2=0,flag3=0;
char usr1[10],usr2[10],usr3[10],newusr1[10],newusr2[10],newusr3[10],b[100];
printf("enter data for user 1\n");
gets(usr1);
printf("enter data for user 2\n");
gets(usr2);
printf("enter data for user 3\n");
gets(usr3);
length[0]=strlen(usr1);
length[1]=strlen(usr2);
length[2]=strlen(usr3);
for(j=0;j<3;j++)
{
length_t+=length[j];
if(maxlength<length[j])
maxlength=length[j];
}

if(length_t%2==0)
frame=length_t/2;
else
frame=(length_t/2)+1;
printf("\ntotal frames are %d\n",frame);

for(i=0;i<maxlength;i++)
{
if(isalpha(usr1[i]))
b[k++]=usr1[i];
if(isalpha(usr2[i]))
b[k++]=usr2[i];
if(isalpha(usr3[i]))
b[k++]=usr3[i];
}
b[k]=NULL;
k=0;
for(i=1;i<=frame;i++)
{
printf("\nframe %d is ",i);
for(j=0;j<2;j++)
printf("%c",b[k++]);
}
k=0;
for(i=0;i<frame;i++)
{
if(i<strlen(usr1))
newusr2[i]=b[k++];
if(i<strlen(usr2))
newusr3[i]=b[k++];
if(i<strlen(usr3))
newusr1[i]=b[k++];
}
newusr1[strlen(usr3)]=NULL;
newusr2[strlen(usr1)]=NULL;
newusr3[strlen(usr2)]=NULL;
printf("\nTransferring Data To Respective Users...\n\n");
printf("user1 gets %s \n",newusr1);
printf("user2 gets %s \n",newusr2);
printf("user3 gets %s \n",newusr3);
return 0;
}