Skip to main content

Floyd’s Algorithm using dynamic Programming in C 

#include< stdio.h >
#include< stdio.h>
#include< conio.h>
#define MAX 30
void floyd(int[MAX][MAX],int);
int mix(int,int);
void main()
{
 int l[MAX][MAX],n,i,j;
 clrscr();

 printf("\n Enter number of vertices you need:");
 scanf("%d",&n);

 printf("\n[Enter 9999 as infinity value]");

 for(i=1;i<= n;i++)
 {
  for(j=1;j<= n;j++)
  {
   printf("\n l[%d][%d]:",i,j);
   scanf("%d",&l[i][j]);
  }
 }
 floyd(l,n);
getch();
}
void floyd(int l[MAX][MAX],int n)
{
 int D[MAX][MAX],p[MAX][MAX],i,j,k;

 for(i=1;i<= n;i++)
  for(j=1;j<= n;j++)
  {
   D[i][j]=l[i][j];
   p[i][j]=0;
  }
 for(k=1;k<= n;k++)
 {
  for(i=1;i<= n;i++)
  {
   for(j=1;j<= n;j++)
   {
    if(D[i][k]+D[k][j] < D[i][j])
    {
     p[i][j]=k;
    }
    D[i][j]=min(D[i][j],D[i][k]+D[k][j]);
   }
  }
  printf("\n--k=%d-------D%d---------\t\t   ---------P%d------",k,k,k);
  for(i=1;i<=n;i++)
  {
   printf("\n ");
   for(j=1;j<= n;j++)
   {
    printf("%5d",D[i][j]);
   }
   printf("\t\t");
   for(j=1;j<= n;j++)
   {
    printf("%5d",p[i][j]);
   }
  }
 }
}
int min(int a,int b)
{
 return a<= b ? a:b;
}

OUTPUT

Enter number of vertices you need:4

[Enter 9999 as infinity value]
 l[1][1]:0

 l[1][2]:5

 l[1][3]:9999 
  
 l[1][4]:9999

 l[2][1]:50

 l[2][2]:0

 l[2][3]:15

 l[2][4]:5

 l[3][1]:30

 l[3][2]:9999

 l[3][3]:0

 l[3][4]:15

 l[4][1]:30

 l[4][2]:9999

 l[4][3]:5

 l[4][4]:0

 l[4][3]:5

 l[4][4]:0

--k=1-------D1---------            ---------P1------
   0     5    9999 9999              0    0    0    0
   50    0       1    5              0    0    0    0
   30   35       0   15              0    1    0    0
   30   35       5    0              0    1    0    0
--k=2-------D2---------            ---------P2------
     0    5      20  10              0    0    2    2
    50    0      15   5              0    0    0    0
    30   35      0   15              0    1    0    0
    30   35      5    0              0    1    0    0
--k=3-------D3---------            ---------P3------
     0    5     20   10              0    0    2    2
    45    0     15    5              3    0    0    0
    30   35      0   15              0    1    0    0
    30   35      5    0              0    1    0    0
--k=4-------D4---------            ---------P4------
     0    5     15   10              0    0    4    2
    35    0     10    5              4    0    4    0
    30   35      0   15              0    1    0    0
    30   35      5    0              0    1    0    0
Labels:

Comments

Post a Comment

Popular posts from this blog

MVT (Multiprogramming Variable Task) in C Programming

#include< stdio.h> #include< conio.h> void main() { int i,os_m,nPage,total,pg[25]; clrscr(); printf("\nEnter total memory size:"); scanf("%d",&total); printf("\nEnter memory for OS:"); scanf("%d",&os_m); printf("\nEnter no. of pages:"); scanf("%d",&nPage); for(i=0;i< nPage;i++) { printf("Enter size of page[%d]:",i+1); scanf("%d",&pg[i]); } total=total-os_m; for(i=0;i< nPage;i++) { if(total>=pg[i]) { printf("\n Allocate page %d",i+1); total=total-pg[i]; } else printf("\n page %d is not allocated due to insufficient memory.",i+1); } printf("\n External Fragmentation is:%d",total); getch(); } OUTPUT Enter total memory size:1024 Enter memory for OS:256 Enter no. of pages:4 Enter size of page[1]:128 Enter size of page[2]:512 Enter size of page[3]:64 Enter size of page[4]:512 Allocate page 1 Al
7 comments
Read more

implement Rail fence cipher in Java

// File Name: RailFence.java import java.util.*; class RailFenceBasic{ int depth; String Encryption(String plainText,int depth)throws Exception { int r=depth,len=plainText.length(); int c=len/depth; char mat[][]=new char[r][c]; int k=0; String cipherText=""; for(int i=0;i< c;i++) { for(int j=0;j< r;j++) { if(k!=len) mat[j][i]=plainText.charAt(k++); else mat[j][i]='X'; } } for(int i=0;i< r;i++) { for(int j=0;j< c;j++) { cipherText+=mat[i][j]; } } return cipherText; } String Decryption(String cipherText,int depth)throws Exception { int r=depth,len=cipherText.length(); int c=len/depth; char mat[][]=new char[r][c]; int k=0; String plainText=""; for(int i=0;i< r;i++) { for(int j=0;j< c;j++) { mat[i][j]=cipherText.charAt(k++); } } for(int i=0;i< c;i++) { for(int j=0;j< r;j++) { plainText+=mat[j][i]; } }
Post a Comment
Read more

Deadlock Prevention using Banker’s Algorithm in C Programming

#include< stdio.h> #include< conio.h> void main() { int allocated[15][15],max[15][15],need[15][15],avail[15],tres[15],work[15],flag[15]; int pno,rno,i,j,prc,count,t,total; count=0; clrscr(); printf("\n Enter number of process:"); scanf("%d",&pno); printf("\n Enter number of resources:"); scanf("%d",&rno); for(i=1;i< =pno;i++) { flag[i]=0; } printf("\n Enter total numbers of each resources:"); for(i=1;i<= rno;i++) scanf("%d",&tres[i]); printf("\n Enter Max resources for each process:"); for(i=1;i<= pno;i++) { printf("\n for process %d:",i); for(j=1;j<= rno;j++) scanf("%d",&max[i][j]); } printf("\n Enter allocated resources for each process:"); for(i=1;i<= pno;i++) { printf("\n for process %d:",i); for(j=1;j<= rno;j++) scanf("%d",&allocated[i][j]); } printf("\n avai
Post a Comment
Read more