Finding Vertical Histogram of given set of data 2

#include <iostream>#include <iomanip>#include <algorithm>#include <string>#include<conio.h>using namespace std;
#define VALS 30
int main ( void ){   int h[VALS] = { 1, 2, 4, 8, 16, 8, 4, 2, 1, 0, 1, 2, 4, 8, 4, 2,1, 0, 1, 2, 4, 8, 16, 8, 4, 8, 4, 2, 1, 0 };   int height=0;   int y,x;   cout.unsetf(ios::right);   cout.setf(ios::left);   cout << endl;   for (x=0; x<VALS; x++) height = max(height, h[x]);   for (y=height; y>=1; y--)   {       cout << setw(3) << y << "|";       for (x=0; x<VALS; x++)           if (h[x]>=y) cout << " *"; else cout << "  ";       cout << endl;   }   cout << "---+" << string(VALS*2, '-') << endl;   cout << "   |";   for (x=0; x<VALS; x++)   {       if (x<26)           cout << " " << char('a'+x);       else           cout << " " << char('A'+x-26);   }   cout << endl << endl;   getch();   return 0;}

Finding Vertical Histogram of given set of data

#include<conio.h>
#include<stdio.h>

int main()
  {
     clrscr();
     int i,j,k,c,num,mrk[10],max,tmp;
     do
     {
     printf("Enter the no. of cases (max. 10): ");
     scanf("%d",&num);
     }while(num<=0 || num>10);
     printf("\n\n");

     max = 0;
     for(i=0;i<num;i++)
     {
 do
      {
printf("\nEnter frequency for Case #%d : ",i+1);
   scanf("%d",&mrk[i]);
 }while( mrk[i]>32766 || mrk[i]<0 );
  if(max < mrk[i])
    max = mrk[i];
     }
     printf("\n\n All data has been collected !!");
     getch();
     clrscr();
     for(i=0;i<num;i++)
     {
      c = (mrk[i]*25)/max;
      //gotoxy(5+(5*i),0);
      for(k=0;k<c;k++)
      {
for(j=0;j<3;j++)
{
gotoxy(5+(5*i)+j,k);
printf("*");

}
      }
      gotoxy(5+(5*i),k);
      printf("%d",mrk[i]);

     }

     getch();
     return 0;
  }

Finding the Saddle Point of Matrix

#include<conio.h>
#include<stdio.h>
#include<math.h>

int main()
  {
    int i,j,m,n,min;
    int mat[10][10];
    printf("\n Enter the no. of rows and columns : ");
    scanf("%d %d",&m,&n);

    for(i=0;i<m;i++)
    {
      printf("Row %d : ",i+1);            
      for(j=0;j<n;j++)
       scanf("%d",&mat[i][j]);  
    }
   
    for(i=0;i<m;i++)
    {
      min = 0;        
      for(j=1;j<n;j++)
      {
        if(mat[i][min] > mat[i][j])
         min = j;            
      }    
      for(j=0;j<m;j++)
      {
        if(mat[j][min] > mat[i][min])
         break;                            
      }
      printf("\n Row %d : ",i+1);
      if(j == m)
       printf("Saddle point exists at Column %d",min+1);
      else
       printf("Saddle point doesn't exists");    
    }    
    getch();
    return 0;
  }

Ordered List

#include<iostream.h>
#include<conio.h>

struct list
{
 int node;
 struct list *nxt;
};

class linked_list
{
 public:
  struct list *start;
  int nol;
   linked_list();
  ~linked_list();
  void insert_node();
  void delete_node();
  void display_list();
};

void linked_list :: linked_list()
{
  nol = 0;
  start = NULL;
}

void linked_list :: ~linked_list()
{
  nol = 0;
  struct list *nptr;
  nptr = start;
  start = NULL;
  delete nptr;
}

void linked_list :: insert_node()
{
 struct list *nptr;
 nptr = new list;
 cout<<"\n Enter the New Node to be Inserted : ";
 cin>>nptr->node;
 nptr->nxt = NULL;

 if(start == NULL)
  start = nptr;
 else
 {
  nptr->nxt = start;
  start = nptr;
 }
 nol += 1;
 cout<<"\n The Node has been Inserted into the List ";
 getch();
}


void linked_list :: delete_node()
{
 if(nol == 0)
  cout<<"\n WARNING !! No more Nodes in the List \n";
 else
 {
 struct list *loc,*locp,*nptr;
 int info;
 cout<<"\n Enter the Node to be Deleted : ";
 cin>>info;
 locp = NULL;
 loc = start;
 while(loc->node != info && loc != NULL)
 {
   locp = loc;
   loc = loc->nxt;
 }
 if(loc == NULL)
  cout<<"\n The Node is not present in the List ";
 else
 {
  nptr = new list;
  if(loc == start)
  {
   nptr = start;
   start = start->nxt;
  }
  else
  {
   nptr = loc;
   locp->nxt = loc->nxt;
  }
  nol -= 1;
  delete nptr;
  cout<<"\n The Node has been Deleted from the List ";
 }
 }
 getch();
}


void linked_list :: display_list()
{
 struct list *ptr;
 cout<<"\n The Linked List : \n\t";
 ptr = start;
 while(ptr != NULL)
 {
  cout<<ptr->node<<" -> ";
  ptr = ptr->nxt;
 }
 cout<<"NULL\n";
 cout<<"\n The Numer of Nodes in this List : "<<nol;
 getch();
}

class ord_linked_list : public linked_list
{
 public:
  ord_linked_list();
  ~ord_linked_list();
  void insert_node();
  void delete_node();
  void display_list();
};

void ord_linked_list :: ord_linked_list()
{
  linked_list::linked_list();
}

void ord_linked_list :: ~ord_linked_list()
{
  linked_list::~linked_list();
}

void ord_linked_list :: insert_node()
{
 struct list *nptr;
 nptr = new list;
 cout<<"\n Enter the New Node to be Inserted : ";
 cin>>nptr->node;
 nptr->nxt = NULL;

 if(start == NULL)
  start = nptr;
 else
 {
  struct list *loc,*locp;
  locp = NULL;
  loc = start;
  while(loc != NULL && loc->node <= nptr->node)
  {
   locp = loc;
   loc = loc->nxt;
  }
  if(loc == NULL)
   locp->nxt = nptr;
  else if(loc == start)
  {
   nptr->nxt = start;
   start = nptr;
  }
  else
  {
   locp->nxt = nptr;
   nptr->nxt = loc;
  }
 }
 nol += 1;
 cout<<"\n The Node has been Inserted into the List ";
 getch();
}


void ord_linked_list :: delete_node()
{
 linked_list::delete_node();
}


void ord_linked_list :: display_list()
{
 linked_list :: display_list();
}

void main()
{
 int cho;
 linked_list ll;
 linked_list();
 do
 {
 clrscr();
 cout<<"\n.. UNORDERED LINKED LIST MENU ..\n";
 cout<<"\n 1. Insert a node";
 cout<<"\n 2. Delete a node";
 cout<<"\n\n  Enter an option : ";
 cin>>cho;
 switch(cho)
 {
  case 1 :  ll.insert_node();
   break;
  case 2 :  ll.delete_node();
   break;
  default:  break;
 }
 ll.display_list();
 }while(cho == 1 || cho == 2);
 getch();


 clrscr();
 ord_linked_list oll;
 ord_linked_list();
 do
 {
 clrscr();
 cout<<"\n.. ORDERED LINKED LIST MENU ..\n";
 cout<<"\n 1. Insert a node";
 cout<<"\n 2. Delete a node";
 cout<<"\n\n  Enter an option : ";
 cin>>cho;
 switch(cho)
 {
  case 1 :  oll.insert_node();
   break;
  case 2 :  oll.delete_node();
   break;
  default:  break;
 }
 oll.display_list();
 }while(cho == 1 || cho == 2);
 getch();
}

Static Huffman Coding

#include<conio.h>
#include <stdio.h>
#define max 0
#define mxbits 20


struct ele
{
  int posn; // Position of the node inside the Huffman tree
  int info;
  int code[mxbits];
  int lft;
  int rgt;
}ar[max],tr[max],item,item1,tmp1,tmp2,tmp3;


int noe,i,j,ptr,par,ind,left,right;


/* Data Items (Internal Nodes) and External Nodes are Inserted in Min Heap */
void ins_heap(int n,struct ele item)
{
 tr[n] = item;
 if(n != 1)
 {
 ptr = n;
 par = ptr/2;


 while(ptr>1 && tr[par].info > tr[ptr].info)
 {
  item = tr[par];
  tr[par] = tr[ptr];
  tr[ptr] = item;
  ptr = par;
  par = ptr/2;
 }


 }
}


/* Data Items (Internal Nodes) and External Nodes are Deleted from the Min Heap */
struct ele del_heap(int end)
{
 item1 = tr[1];
 tr[1] = tr[end];
 par = 1; left = 2; right = 3;
 ind = 0;


 while(par < end && ind == 0)
 {
  if(tr[left].info < tr[par].info && tr[left].info < tr[right].info && left<end)
  {
  item = tr[left];
  tr[left] = tr[par];
  tr[par] = item;
  par = left;
  }


  else if(tr[right].info < tr[par].info && tr[left].info > tr[right].info  && right<end)
  {
  item = tr[right];
  tr[right] = tr[par];
  tr[par] = item;
  par = right;
  }
  else
   ind = 1;
  left = 2*par;
  right = 2*par+1;
 }
 return item1;
}


/* Insertion of data items in an arrays as well as on the Min-Heap
Here, every Data Items will be treated as Internal Nodes of the Huffman Tree */


void inp_dat()
{
 do
 {
 printf("\n\n Enter the no. of data items : ");
 scanf("%d",&noe);
 }while(noe<=0 || noe>=max/2);


 printf("\n\n Enter the frequencies '%d' data items : ",noe);

for(i=1;i<=noe;i++)
  {
  scanf("%d",&ar[i].info);
  ar[i].posn = 0;
  ar[i].lft = 0;
  ar[i].rgt = 0;
  ins_heap(i,ar[i]);
  }
}


/* The following Function performs to Form a Huffman Tree
After Forming a Min-Heap of Data Items, Two of them are Popped from the heap and 
added together to form an External node, which is again Inserted to the Min-Heap */


void hfmn_tree()
{
 i = noe;
 j = i+1;


 while(i>1)
 {
  tmp1 = del_heap(i);
  tmp2 = del_heap(--i);
  tmp3.info = tmp1.info + tmp2.info;
  tmp3.posn = j;
  tmp3.lft = tmp1.posn;
  tmp3.rgt = tmp2.posn;
  ar[j] = tmp3;
  ins_heap(i,tmp3);
  j++;
 }


 ar[j-1].posn = 1; // Sets the position of Root of Huffman Tree to ‘1’
 i = j-1;
// Sets the position of External Nodes & Internal Nodes as Data Items of Huffman Tree
 while(i > noe)
 {
  ar[ar[i].lft].posn = 2*ar[i].posn;
  ar[ar[i].rgt].posn = 2*ar[i].posn+1;
  i--;
 }
}






/* After getting the position of every Data Items (Internal Nodes of Huffman Tree)
  We’ve to find out the codes of every Data Item  */


void codes()
{
  int k;
  char ch;


/* The code of every Data Item is obtained by Dividing its Huffman Tree position by 2 
  And storing its remainder until it becomes less than 1 */


  printf("\n The Codes for every input is : ");
  for(i=1;i<=noe;i++)
  {
   k = 0;
   ch = 64+i;
   printf(" \n For %c = %d : ",ch,ar[i].info);
   while(ar[i].posn > 1)
   {
   ar[i].code[k] = ar[i].posn % 2;
   ar[i].posn /= 2;
   k++;
   }
   for(j=k-1;j>=0;j--) // Codes are printed in Reversed Order
    printf("%d",ar[i].code[j]);
  }
}


void main()
{
clrscr();
inp_dat();
hfmn_tree();
codes();
getch();
}

Dynamic Huffman Coding

#include<stdio.h>
#include<conio.h>
#include<ctype.h>
#include<math.h>
#define max 50 
#define ascmax 130


struct tree
{
  int posn;     
  char ct;
  int frq;     
  int rgt;     
  int lft;       
}tr[ascmax+max];






int size =2;
int epos;




void init_node(char tmp)
{
  tr[0].posn = 1;
  tr[0].ct = '~'; 
  tr[0].lft = 1;
  tr[0].rgt = 2;
  tr[0].frq = 1; 
  
  tr[1].posn = 2*tr[0].posn;
  tr[1].ct = 'E';
  tr[1].frq = 0;
  
  tr[2].posn = 2*tr[0].posn+1;
  tr[2].ct = tmp;
  tr[2].frq = 1;
    
  tr[1].lft = tr[2].lft = -1;
  tr[1].rgt = tr[2].rgt = -1;  


  epos = 1;
  
  printf("\n '%c'\t\t '%c'",tmp,tmp);
  printf("\n Traversing :- ('E',0) ('%c',1)",tmp); 
  printf("\n The Tree is in weight order\n"); 
}






void add_node(char ctc)
{
 char bits[max];
 int bsize=0,ps,j; 

 printf("\n '%c'\t\t '%c' ",ctc,ctc);
 int tp = tr[epos].posn;
 while(tp > 1)
 {
   bits[bsize] = 48+(tp%2);
   tp /= 2;      
   ++bsize;         
 }  
 for(tp=bsize-1;tp>=0;tp--)
  printf("%c",bits[tp]); 

 ++size;
 tr[size] = tr[epos];
 tr[size].posn = 2*tr[epos].posn;
 tr[size].lft = -1;    
 tr[size].rgt = -1;    



 tr[epos].ct = '^';
 tr[epos].frq = 1;    
 tr[epos].lft = size;    
 tr[epos].rgt = size+1;    




 epos = size;

 ++size;

 tr[size].posn = tr[epos].posn+1;
 tr[size].ct = ctc;
 tr[size].frq = 1;
 tr[size].lft = -1;
 tr[size].rgt = -1;  

 ps = (tr[size].posn/2)/2;
  

  
  while(ps >= 1)
  {
   j = 0;
   while(tr[j].posn != ps)
    j++;
   
   tr[j].frq += 1;         
   ps /= 2;           
  }  



}




void update_node(char ctc)
{
  char bits[max];
 int bsize=0;    

  int i=1,j;
  int ps;
  while(ctc != tr[i].ct)
   i++; 
    
  tr[i].frq += 1;
  
  ps = tr[i].posn/2;
  

  
  while(ps >= 1)
  {
   j = 0;
   while(tr[j].posn != ps)
    j++;
   

   tr[j].frq += 1;         
   ps /= 2;           
  }  
  
  printf("\n '%c'\t\t   ",ctc);
 int tp = tr[i].posn;
 while(tp > 1)
 {
   bits[bsize] = 48+(tp%2);
   tp /= 2;      
   ++bsize;         
 }  
 for(tp=bsize-1;tp>=0;tp--)
  printf("%c",bits[tp]); 

}


void reset_node(int nm)
{
 ///printf("\n\n %c/%d(pos=%d)",tr[nm].ct,tr[nm].frq,tr[nm].posn);    
 if(tr[nm].ct == 'E')
  epos = nm;
  
 if(tr[nm].lft != -1)
 {
   //printf("\n Lft Case");            
   tr[tr[nm].lft].posn = 2*tr[nm].posn;
   reset_node(tr[nm].lft);        
 }

 if(tr[nm].rgt != -1 )
 {
   //printf("\n Rgt Case");
   tr[tr[nm].rgt].posn = 2*tr[nm].posn+1;
   reset_node(tr[nm].rgt);      
 }
     
}


void balance_tree()
{
  //printf("\n%d",tr[epos].posn);
  struct tree tn;
  double lvl;
  int i,ilvl,j,ind;
  int optnsize;
  int init; 
  //= tr[epos].posn;
  
  struct outptn
  {
   int psn;
   int frq;      
  }optn[ascmax+max];
  
 do
 {
  optnsize = 0;
  //printf("\n %d %d %c",epos,tr[epos].posn,tr[epos].ct);
  
  lvl = log((double)tr[epos].posn)/log (2);
  ilvl = (int) lvl;
  init = tr[epos].posn;
  
 // printf("\n level=%d ",ilvl);
  while(ilvl>0)
  {
    for(i=init;i<=pow(2,ilvl+1)-1;i++)
    {
      j = 0;
      while(j<=size && tr[j].posn != i)
       j++;    
      if(j<=size)
      {
        optn[optnsize].psn = j;
        optn[optnsize].frq = tr[j].frq;
        ++optnsize;         
      }        
    }    
    --ilvl;     
    init = pow(2,ilvl);          
  }
    
  optn[optnsize].psn = 0;
  optn[optnsize].frq = tr[0].frq;
  ++optnsize;      
  
  ind = -1;
  printf("\n Traversing :-");
  for(i=0;i<optnsize;i++)  
  {
    printf(" ('%c',%d)",tr[optn[i].psn].ct,optn[i].frq);
     if(i < optnsize-1 && optn[i].frq > optn[i+1].frq && ind == -1)
       ind = i;   
  } 
  
  if(ind != -1)
  {
   printf("\n The Tree is not in weight order");     
   
   int ind2 = ind+1;
   
   while(optn[ind2].frq == optn[ind2+1].frq)
    ind2++;
   
   while(optn[ind].frq == optn[ind-1].frq)
    ind--;
    
   printf("\n Swapping ('%c',%d) and ('%c',%d)",tr[optn[ind].psn].ct,optn[ind].frq,tr[optn[ind2].psn].ct,optn[ind2].frq);
   
   int tmp = tr[optn[ind].psn].posn;
     tmp /= 2;
     int k=0;
   
     while(tr[k].posn != tmp)
      k++;
      
   tmp = tr[optn[ind2].psn].posn;
     tmp /= 2;
     int l=0;
     while(tr[l].posn != tmp)
      l++;
     
      
     if(tr[optn[ind].psn].posn%2 == 0)
     {
      tmp = tr[k].lft;                           
      tr[k].lft = optn[ind2].psn;
      if(tr[optn[ind2].psn].posn%2 == 0)
      {
       tr[l].lft = tmp;  
       tr[tr[l].lft].posn = 2*tr[l].posn;
      }
      else
      { 
       tr[l].rgt = tmp;
       tr[tr[l].rgt].posn = 2*tr[l].posn+1;
      }
      tr[tr[k].lft].posn = 2*tr[k].posn;
     }
     
     else
     {
      tmp = tr[k].rgt;                           
      tr[k].rgt = optn[ind2].psn;
      if(tr[optn[ind2].psn].posn%2 == 0)
      {
       tr[l].lft = tmp;  
       tr[tr[l].lft].posn = 2*tr[l].posn;
      }
      else
      { 
       tr[l].rgt = tmp;
       tr[tr[l].rgt].posn = 2*tr[l].posn+1;
      }
      tr[tr[k].rgt].posn = 2*tr[k].posn+1;
     }
     
     

   reset_node(optn[ind].psn);
   reset_node(optn[ind2].psn);     
   
   for(j=size;j>=0;j--) 
   {
     if(tr[j].ct == '~' || tr[j].ct == '^') 
       tr[j].frq = tr[tr[j].lft].frq + tr[tr[j].rgt].frq ;              
   }    
  }
  else
   printf("\n The Tree is in weight order");  
  optnsize = 0;
 }while(ind != -1);
 printf("\n");
}




int main()
{
 char msg[max]; 
 printf("\n Enter the string : "); 
 gets(msg);
 printf("\n Dynamic Huffman Coding \n");
 printf("\n Input\t\t Output");
 printf("\n -----\t\t ------\n");
  int i=1;
 int j; 
 init_node(msg[0]);
 while(msg[i]!='\0')
 {
   j=i;
   do
   {
     --j;  
   }while(j>=0 && msg[j] != msg[i]);     
   if(j>=0)
    update_node(msg[i]);
   else
    add_node(msg[i]);
   balance_tree();
  i++;   
  getch(); 
 }
 getch();
 return 0;   
}

Floyd-Warshall Algorithm 2

#include<conio.h>

#include<stdio.h>

#define INFNITY 999

int a[10][10],n;

voidprintArray(){

inti,j;

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

    {

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

        {

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

        }

printf("\n");

    }

}

voiduAdjacencyMatrix(){

inti,j,c=1,w;

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

    {

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

        {

a[i][j] = INFNITY ;

a[j][i] = INFNITY ;

        }

a[i][i] = 0;   

    }

while(c!=-1)

    {

printf ("\ni , j , w :");           

scanf("%d%d%d",&i,&j,&w);

a[i][j]=w;

     //printf ("c? :");

scanf("%d",&c);

    }

printArray();

getch();

}

int main()

{

int d[10][10], da[10][10],i,j,l,m,k;

printf("enter the number of vertices : ");

scanf("%d",&n);

uAdjacencyMatrix();

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

 {

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

                 {

d[i][j]=a[i][j];

                 }

 }

for(k=0;k<n;k++)

{

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

                 {

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

                     {

if(d[i][j]<d[i][k]+d[k][j])

                                 {

da[i][j]=d[i][j];

                                 }

else

                                 {

da[i][j]=d[i][k]+d[k][j];

                                 }

                     }

                 }

for(l=0;l<n;l++)

                 {

for(m=0;m<n;m++)

                                 {

d[l][m]=da[l][m];

                                 }

                 }

}                

for(l=0;l<n;l++)

                 {

printf("\n");

for(m=0;m<n;m++)

                                 {

printf("%d\t\t",da[l][m]);

                                 }

                 }                

getch();

return(0);

}

Longest Common Sub-sequence 2

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#include<string.h>

char a[10],b[10];

int count[10][10],dir[10][10];

void backtrack(int i, int j)

{

if(i!=0 && j!=0)

  {

if(dir[i][j] == 3)

    {

backtrack(i-1,j-1);

printf("%c",a[i-1]);        

    }     

else if(dir[i][j] == 2)

backtrack(i-1,j);

else

backtrack(i,j-1);

  }  

}

int main()

{

                int i,j,k,count1,count2;

                printf("\n Enter 1st string : ");

gets(a);

fflush(stdin);

printf("\n Enter 2nd string : ");

gets(b);

                count1 = strlen(a);

    count2 = strlen(b);

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

                count[i][0]=0;

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

                count[0][i]=0;

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

                {

                                for(j=1;j<=count2;j++)

                                {

                                                if(a[i-1]==b[j-1])

                                                {

                                                                count[i][j]=count[i-1][j-1]+1;

                                                                dir[i][j]=3;

                                                }

                                                else if(count[i][j-1]>=count[i-1][j])

                                                {

                                                                count[i][j]=count[i][j-1];

                                                                dir[i][j]=1;

                                                }

                                                else

                                                {

                                                                count[i][j]=count[i-1][j];

                                                                dir[i][j]=2;

                                                }

                                }

                }

                char temp;

                i=0;

                while(i<count2)

                {

                printf("%c\t",b[i]);

                i++;

    }

                printf("\n");

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

                {

printf("%c",a[i-1]);

                                for(j=1;j<=count2;j++)

                                {

                                                if(dir[i][j]==1)

                                                temp='-';

                                                else if(dir[i][j]==2)

                                                temp='|';

                                                else if(dir[i][j]==3)

                                                temp='\\';

                                                printf("%c%d\t",temp,count[i][j]);

                                }

                                printf("\n");

                }             

printf("The LCS is : ");

backtrack(count2,count1);          

getch();

return(0);

}

Floyd-Warshall Algorithm

#include<stdio.h>
#include<conio.h>
#define max 10
#define INFINITY 1000

int w[max+1][max+1];
int n_size;

int d[max+1][max+1][max+1];
int pi[max+1][max+1][max+1];

void in_dat()
{
 printf("\n Enter the number of nodes : ");
 scanf("%d",&n_size);

 int i;

 for(i=1;i<=n_size;i++)
 {
  w[i][i] = 0;
  d[0][i][i] = 0;
  pi[0][i][i] = 0;

  for(int j=i+1;j<=n_size;j++)
  {
   printf("\n Enter the weight of edge '%d' to '%d': ",i,j);
   scanf("%d",&w[i][j]);
   if(w[i][j] == 0)
    w[i][j] = INFINITY;

   d[0][i][j] = w[i][j];
   pi[0][i][j] = w[i][j] == INFINITY ? 0:i;

   printf("\n Enter the weight of edge '%d' to '%d': ",j,i);
   scanf("%d",&w[j][i]);
   if(w[j][i] == 0)
    w[j][i] = INFINITY;

   d[0][j][i] = w[j][i];
   pi[0][j][i] = w[j][i] == INFINITY ? 0:j;
  }
 }
}

void flyd_wrsl()
{
 int i,j,k,m;

 printf("\n\n\t D(0)/Pi(0)");

 for(i=1;i<=n_size;i++)
 {
  printf("\n");
  for(j=1;j<=n_size;j++)
  {
   if(d[0][i][j] == INFINITY)
    printf("\t*");



   else
    printf("\t%d",d[0][i][j]);
   printf("/%d",pi[0][i][j]);
  }
 }

 getch();

 for(k=1;k<=n_size;k++)
 {
  printf("\n\n\t D(%d)/Pi(%d)",k,k);
  for(i=1;i<=n_size;i++)
  {
   printf("\n");

   for(j=1;j<=n_size;j++)
   {
    if(d[k-1][i][j] > d[k-1][i][k] + d[k-1][k][j])
    {
     pi[k][i][j] = pi[k-1][k][j];
     if(d[k-1][i][k] != INFINITY && d[k-1][k][j] != INFINITY)
      d[k][i][j] = d[k-1][i][k] + d[k-1][k][j];
     else
      d[k][i][j] = d[k-1][i][j];
    }

    else
    {
     pi[k][i][j] = pi[k-1][i][j];
     d[k][i][j] = d[k-1][i][j];
    }

    if(d[k][i][j] == INFINITY)
     printf("\t*");
    else
     printf("\t%d",d[k][i][j]);
    printf("/%d",pi[k][i][j]);
   }
  }
  getch();

 }
}

int main()
{
 in_dat();
 flyd_wrsl();
 getch();
 return 0;
}

Bellman's Ford Algorithm

#include<stdio.h>
#include<conio.h>
#define max 10
#define INFINITY 1000

char node[max];
int ind[max];

int d[max];
char p[max];
int w[max][max];
char edge[2*max*max][2];

int e_size;
int n_size;

void in_dat()
{
 printf("\n Enter the number of nodes : ");
 scanf("%d",&n_size);
 fflush(stdin);

 for(int i=0;i<n_size;i++)
  node[i] = 97+i;

 e_size = 0;

 for(int i=0;i<n_size;i++)
 {
  w[i][i] = 0;

  for(int j=i+1;j<n_size;j++)
  {
   printf("\n Enter the weight of edge '%c' to '%c': ",97+i,97+j);
   scanf("%d",&w[i][j]);

   if(w[i][j] != 0)
   {
    edge[e_size][0] = 97+i;  
    edge[e_size][1] = 97+j;
    e_size++;
   }

   printf("\n Enter the weight of edge '%c' to '%c': ",97+j,97+i);
   scanf("%d",&w[j][i]);
   if(w[j][i] != 0)
   {
    edge[e_size][0] = 97+j;  
    edge[e_size][1] = 97+i;
    e_size++;
   }
  }
 }
}

void dis_dat()
{
 printf("\n The Path adjacent matrix \n");
 for(int i=0;i<n_size;i++)
  printf("\t%c",97+i);


 for(int i=0;i<n_size;i++)
 {
  printf("\n%c",97+i);
  for(int j=0;j<n_size;j++)
   printf("\t%d",w[i][j]);
 }
}

void bellford()
{
 char s;
 do
 {
 printf("\n Enter the starting point : ");
 scanf("%c",&s);
 }while(s<97||s>=97+n_size);

 for(int i=0;i<n_size;i++)
 {
  d[i] = INFINITY;
  p[i] = ' '; // NULL here
 }

 int si = s-97;
 d[si] = 0;

 int in=0,min,dd,tp;

 while(in < n_size-1)
 {
  for(int i=0;i<e_size;i++)
  {
   if(d[edge[i][1]-97] > d[edge[i][0]-97] + w[edge[i][0]-97][edge[i][1]-97])
   {
     d[edge[i][1]-97] = d[edge[i][0]-97] + w[edge[i][0]-97][edge[i][1]-97];
     p[edge[i][1]-97] = edge[i][0];
   }
  }
  ++in;
 }

 printf("\n ..... The Results ..... \n");
 printf("\n \td\tp");

 for(int i=0;i<n_size;i++)
  printf("\n%c\t%d\t%c",node[i],d[i],p[i]);

getch();
}

int main()
{
 in_dat();
 dis_dat();
 bellford();
 getch();
 return 0;
}

Dijkstra's Algorithm 2

#include<conio.h>

#include<stdio.h>

#define INFNITY 999

int a[10][10],p[10],d[10],n;

voidprintArray(){

inti,j;

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

    {

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

        {

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

        }

printf("\n");

    }

}

voiduAdjacencyMatrix(){

inti,j,c=1,w;

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

    {

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

        {

a[i][j] = INFNITY;

a[j][i] = INFNITY;

        }

a[i][i] = INFNITY;

    }

while(c!=-1)

    {

printf ("\ni , j , w :");           

scanf("%d%d%d",&i,&j,&w);

a[i][j]=w;

     //printf ("c? :");

scanf("%d",&c);

    }

printArray();

getch();

}

voidinitializeSingleSource(int i)

{

int j;

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

     {

p[j]=-1;

d[j]=INFNITY;

     }

d[i]=0;

}           

voidtracePath(int a)

{

if(p[a]!=-1)

tracePath(p[a]);

printf("-->%d",a);

}

voidshowAllPaths()

{

int i;

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

    {

if(p[i]!=-1)

printf("\n%d-->%d",p[i],i);    

    }

}

int main()

{

inti,j,k;

printf("enter the number of vertices : ");

scanf("%d",&n);

uAdjacencyMatrix();

printf("enter the  source vertex : ");

scanf("%d",&i);

initializeSingleSource(i);

for(i=0;i<n-1;i++)

    {

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

        {

for(k=0;k<n;k++)

           {

if((a[j][k]!=INFNITY)&& d[k]>d[j]+a[j][k])

                  {

p[k]=j;

d[k]=d[j]+a[j][k];

                  }

           }             

        } 

    }

int t=0;

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

        {

for(k=0;k<n;k++)

           {

if((a[j][k]!=INFNITY)&& d[k]>d[j]+a[j][k])

                  {

                     t=-1;

                  }

if(t==-1)

break;    

           }             

if(t==-1)

break;    

        }

if(t==-1)

printf("\nexiting");

showAllPaths();

printf("\n Enter the vertex for shortest path : ");

scanf("%d",&i);

tracePath(i);

getch();

return(0);

}