Floyd's Algorithm

ALGORITHM Floyd(W [1..n, 1..n])

//Implements Floyd’s algorithm for the all-pairs shortest-paths problem
//Input: The weight matrix W of a graph with no negative-length cycle
//Output: The distance matrix of the shortest paths’ lengths

D ← W //is not necessary if W can be overwritten

for k ← 1 to n do
for i ← 1 to n do
for j ← 1 to n do
D[i, j] ← min{D[i, j], D[i, k] + D[k, j]}

return D 


C Program:

#include<stdio.h>
void main()
{

    int i,j,k,n,a[10][10],d[10][10];

    printf("enter the no of vertices\n");
    scanf("%d",&n);
    printf("enter the cost matrix\n");
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    {
        printf("enter 0 for self loops & 999 for no edges\n");
        printf("enter edges from %c to %c\n",i+64,j+64);
        scanf("%d",&a[i][j]);
        d[i][j]=a[i][j];
    }
    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])
    d[i][j]=d[i][k]+d[k][j];
    printf("All pairs shortest path\n");
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        printf("%5d",d[i][j]);
        printf("\n");
    }
}

Output:

enter the no of vertices
4
enter the cost matrix
enter 0 for self loops & 999 for no edges
enter edges from A to A
0
enter 0 for self loops & 999 for no edges
enter edges from A to B
3
enter 0 for self loops & 999 for no edges
enter edges from A to C
999
enter 0 for self loops & 999 for no edges
enter edges from A to D
3
enter 0 for self loops & 999 for no edges
enter edges from B to A
2
enter 0 for self loops & 999 for no edges
enter edges from B to B
0
enter 0 for self loops & 999 for no edges
enter edges from B to C
4
enter 0 for self loops & 999 for no edges
enter edges from B to D
999
enter 0 for self loops & 999 for no edges
enter edges from C to A
999
enter 0 for self loops & 999 for no edges
enter edges from C to B
4
enter 0 for self loops & 999 for no edges
enter edges from C to C
0
enter 0 for self loops & 999 for no edges
enter edges from C to D
3
enter 0 for self loops & 999 for no edges
enter edges from D to A
3
enter 0 for self loops & 999 for no edges
enter edges from D to B
999
enter 0 for self loops & 999 for no edges
enter edges from D to C
3
enter 0 for self loops & 999 for no edges
enter edges from D to D
0
All pairs shortest path
    0    3    6    3
    2    0    4    5
    6    4    0    3
    3    6    3    0