/* 8(b). W.A.P. to implement all pairs shortest path problem using the dynamic programming. */

#include<stdio.h>
#include<conio.h>
int Min(int a,int b)
{
    return ((a < b) ? a : b);
}
void main()
{
    int i,j,k,a[10][10],cost[10][10],n;
    clrscr();
    printf("\nEnter the no. of vertices: ");
    scanf("%d",&n);
    printf("\nEnter the cost matrix [Indicate 99 for no edge]: \n");
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
        {
            scanf("%d",&cost[i][j]);
                if (i == j)
                    cost[i][j] = 0;
                    a[i][j] = cost[i][j];
        }
        for (k = 0; k < n; k++)
            for (i = 0; i < n; i++)
                for (j = 0; j < n; j++)
                    a[i][j] = Min(a[i][j], a[i][k] + a[k][j]);
                    printf("\nShortest Path matrix is :\n");
                for (i = 0; i < n; i++)
                {
                    for (j = 0; j < n; j++)
                        printf("%d ",a[i][j]);
                        printf("\n");
                 }
    getch();
}
/* OUTPUT
Enter the no. of vertices : 4
Enter the cost matrix :
0 10 1000 40
1000 0 1000 20
50 1000 0 1000
1000 1000 60 0

Shortest Path matrix is :
0 10 90 30
130 0 80 20
50 60 0 80
110 120 60 0
*/