/*
FLOYD
*/



#include<stdio.h>

void main()
{
int wt[10][10],n,i,j;
void floyds(int wt[10][10],int n);

printf("\nHow many vertices you want");
scanf("%d",&n);
printf("Enter the elements");
printf("Enter 999 as infinity value");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("\n wt[%d][%d]",i,j);
scanf("%d",&wt[i][j]);
}
}
printf("\n\tComputing All pair shortest path...\n");
floyds(wt,n);

}

void floyds(int wt[10][10],int n)
{
int d[5][10][10],i,j,k;
int min(int,int);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
d[0][i][j]=wt[i][j];
}
}

for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
d[k][i][j]=min(d[k-1][i][j],(d[k-1][i][k]+d[k-1][k][j]));
}
}
}
for(k=0;k<=n;k++)
{
printf("r(%d)=\n",k);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d\t",d[k][i][j]);
}
printf("\n");
}
}
}
int min(int a, int b)
{
if(a<b)
return a;
else
return b;
}


/*
Output:
ProfessionalCipher@www.professionalcipher.blogspot.com:~$ cd Desktop
ProfessionalCipher@www.professionalcipher.blogspot.com:~/Desktop$ cd print
ProfessionalCipher@www.professionalcipher.blogspot.com:~/Desktop/print$ ls
a.out      floyd.c   nqueen.c~       pipe5a.c   st.c~         strassen_d.c~     str.c~      warshall.c
assTemp.c  floyd.c~  outputfile.txt  pipe5a.c~  strass.c      strassens_method  test1.txt   warshall.c~
FILE1.ASM  nqueen.c  pass.c          st.c       strassen_d.c  str.c             test1.txt~
ProfessionalCipher@www.professionalcipher.blogspot.com:~/Desktop/print$ gcc floyd.c
ProfessionalCipher@www.professionalcipher.blogspot.com:~/Desktop/print$ ./a.out

How many vertices you want3
Enter the elementsEnter 999 as infinity value
 wt[1][1]0

 wt[1][2]8

 wt[1][3]5

 wt[2][1]2

 wt[2][2]0

 wt[2][3]999

 wt[3][1]999

 wt[3][2]1

 wt[3][3]0

 Computing All pair shortest path...
r(0)=
0 8 5 
2 0 999 
999 1 0 
r(1)=
0 8 5 
2 0 7 
999 1 0 
r(2)=
0 8 5 
2 0 7 
3 1 0 
r(3)=
0 6 5 
2 0 7 
3 1 0 
ProfessionalCipher@www.professionalcipher.blogspot.com:~/Desktop/print$ 

*/





/*
Output:
ProfessionalCipher@www.professionalcipher.blogspot.com:~$ cd Desktop
ProfessionalCipher@www.professionalcipher.blogspot.com:~/Desktop$ cd print
ProfessionalCipher@www.professionalcipher.blogspot.com:~/Desktop/print$ ls
a.out      floyd.c   nqueen.c~       pipe5a.c   st.c~         strassen_d.c~     str.c~      warshall.c
assTemp.c  floyd.c~  outputfile.txt  pipe5a.c~  strass.c      strassens_method  test1.txt   warshall.c~
FILE1.ASM  nqueen.c  pass.c          st.c       strassen_d.c  str.c             test1.txt~
ProfessionalCipher@www.professionalcipher.blogspot.com:~/Desktop/print$ gcc warshall.c
ProfessionalCipher@www.professionalcipher.blogspot.com:~/Desktop/print$ ./a.out

 enter no of nodes3
enter adjency matrix
0
1
1
1
0
1
1
1
0


adjency matrix is:
0 1 1 
1 0 1 
1 1 0 

 intermediate matrix t[0]:
0 1 1 
1 1 1 
1 1 1 

 intermediate matrix t[1]:
1 1 1 
1 1 1 
1 1 1 

 intermediate matrix t[2]:
1 1 1 
1 1 1 
1 1 1 

the path matrix is:
1 1 1 
1 1 1 
1 1 1 
ProfessionalCipher@www.professionalcipher.blogspot.com:~/Desktop/print$ 



*/

**********************************************************

FLOYDWARSHALL

*********************************************************

// C Program for Floyd Warshall Algorithm
#include<stdio.h>
 
// Number of vertices in the graph
#define V 4
 
/* Define Infinite as a large enough value. This value will be used
  for vertices not connected to each other */
#define INF 99999
 
// A function to print the solution matrix
void printSolution(int dist[][V]);
 
// Solves the all-pairs shortest path problem using Floyd Warshall algorithm
void floydWarshall (int graph[][V])
{
    /* dist[][] will be the output matrix that will finally have the shortest 
      distances between every pair of vertices */
    int dist[V][V], i, j, k;
 
    /* Initialize the solution matrix same as input graph matrix. Or 
       we can say the initial values of shortest distances are based
       on shortest paths considering no intermediate vertex. */
    for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
            dist[i][j] = graph[i][j];
 
    /* Add all vertices one by one to the set of intermediate vertices.
      ---> Before start of a iteration, we have shortest distances between all
      pairs of vertices such that the shortest distances consider only the
      vertices in set {0, 1, 2, .. k-1} as intermediate vertices.
      ----> After the end of a iteration, vertex no. k is added to the set of
      intermediate vertices and the set becomes {0, 1, 2, .. k} */
    for (k = 0; k < V; k++)
    {
        // Pick all vertices as source one by one
        for (i = 0; i < V; i++)
        {
            // Pick all vertices as destination for the
            // above picked source
            for (j = 0; j < V; j++)
            {
                // If vertex k is on the shortest path from
                // i to j, then update the value of dist[i][j]
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
 
    // Print the shortest distance matrix
    printSolution(dist);
}
 
/* A utility function to print solution */
void printSolution(int dist[][V])
{
    printf ("Following matrix shows the shortest distances"
            " between every pair of vertices \n");
    for (int i = 0; i < V; i++)
    {
        for (int j = 0; j < V; j++)
        {
            if (dist[i][j] == INF)
                printf("%7s", "INF");
            else
                printf ("%7d", dist[i][j]);
        }
        printf("\n");
    }
}
 
// driver program to test above function
int main()
{
    /* Let us create the following weighted graph
            10
       (0)------->(3)
        |         /|\
      5 |          |
        |          | 1
       \|/         |
       (1)------->(2)
            3           */
    int graph[V][V] = { {0,   5,  INF, 10},
                        {INF, 0,   3, 15},
                        {INF, INF, 0,   1},
                        {INF, INF, INF, 0}
                      };
 
    // Print the solution
    floydWarshall(graph);
    return 0;
}



*********************************************************

WARSAHLL

*********************************************************

/*
Assignment no-3
*/

#include<stdio.h>
void warshall(int [10][10],int);
void main()
 {
  int a[10][10],i,j,n;
  
  printf("\n enter no of nodes");
  scanf("%d",&n);
  printf("enter adjency matrix\n");
   
   for(i=0;i<n;i++)
   for(j=0;j<n;j++)

   scanf("%d",&a[i][j]);
   printf("\n\nadjency matrix is:\n");
   
    for(i=0;i<n;i++)
    {
     for(j=0;j<n;j++)
     {
      printf("%d\t",a[i][j]);
     }
       printf("\n"); 
    }
 warshall(a,n);

 }

void warshall(int p[10][10],int n)
{
 int i,j,k,x,y;
 for(k=0;k<n;k++)

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

  {
   for(i=0;i<n;i++)
   {
    if((p[i][j]==0) && (p[i][k]==1) && (p[k][j]==1))

    {
     p[i][j]=1;
    }
   }
  }
 printf("\n intermediate matrix t[%d]:\n",k);
  for(x=0;x<n;x++)
 {
  for(y=0;y<n;y++)
  {
   printf("%d\t",p[x][y]);
  }
  printf("\n");
 }
 }

printf("\nthe path matrix is:\n");

for(i=0;i<n;i++)
 {
  for(j=0;j<n;j++)
   {
    printf("%d\t",p[i][j]);
  
   }
  printf("\n");
 }
}



/*
Output:
ProfessionalCipher@www.professionalcipher.blogspot.com:~$ cd Desktop
ProfessionalCipher@www.professionalcipher.blogspot.com:~/Desktop$ cd print
ProfessionalCipher@www.professionalcipher.blogspot.com:~/Desktop/print$ ls
a.out      floyd.c   nqueen.c~       pipe5a.c   st.c~         strassen_d.c~     str.c~      warshall.c
assTemp.c  floyd.c~  outputfile.txt  pipe5a.c~  strass.c      strassens_method  test1.txt   warshall.c~
FILE1.ASM  nqueen.c  pass.c          st.c       strassen_d.c  str.c             test1.txt~
ProfessionalCipher@www.professionalcipher.blogspot.com:~/Desktop/print$ gcc warshall.c
ProfessionalCipher@www.professionalcipher.blogspot.com:~/Desktop/print$ ./a.out

 enter no of nodes3
enter adjency matrix
0
1
1
1
0
1
1
1
0


adjency matrix is:
0 1 1 
1 0 1 
1 1 0 

 intermediate matrix t[0]:
0 1 1 
1 1 1 
1 1 1 

 intermediate matrix t[1]:
1 1 1 
1 1 1 
1 1 1 

 intermediate matrix t[2]:
1 1 1 
1 1 1 
1 1 1 

the path matrix is:
1 1 1 
1 1 1 
1 1 1 
ProfessionalCipher@www.professionalcipher.blogspot.com:~/Desktop/print$ 



*/