Tweet
# include<stdio.h>
# define size 20
# define infinity 999999
int a[size][size];
int m[size][size];
int i,k,j;
int n;
void Input ();
void Short ();
void Output ();
void Input()
{
printf("\n Input the number of vetices: ");
scanf("%d", &n);
printf("\n Input adjacency matrix\n");
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
scanf("%d", &a[i][j]);
}
printf("\n");
}
printf("\n Adjacency matrix \n");
for ( i = 0; i < n; i++)
{
for ( j = 0; j < n; j++)
{
printf(" %i", a[i][j]);
}
printf("\n");
}
}
void Output()
{
for ( i = 0; i < n; i++)
{
for ( j = 0; j < n; j++)
{
printf(" %d", m[i][j]);
}
printf("\n");
}
}
void Short ()
{
for ( i = 0; i < n; i++)
{
for ( j = 0; j < n; j++)
{
if (a[i][j] == 0)
m[i][j] = infinity;
else
m[i][j] = a[i][j];
}
}
printf("\n Adjacency matrix after replacing zeros by very large value");
Output();
for ( k = 0; k < n; k++)
{
for ( i = 0; i < n; i++)
{
for ( j = 0; j < n; j++)
{
if ( m [i][j] <= m [i][k] + m [k][j] )
m [i][j] = m [i][j];
else
m [i][j] = m[i][k] + m [k][j];
}
}
printf("\n STEP %d \n", k);
Output();
}
}
main()
{
Input();
Short();
printf("\n Shortest path matrix is as follows\n");
Output();
}
Shortest Path Algorithm Programming in C
