General Discussions

Floyd’s Algorithm – C Implementation

All pair shortest path algorithm (Floyd) , C implementation is below. Also available in Github here.

#include 
#include 

int main()
{
    int n = 4;
    int i, j, k;
    int D[5][5] = {
                    {0, 0, 0, 0, 0},
                    {0, 0, 999, 3, 999},
                    {0, 2, 0, 999, 999},
                    {0, 999, 7, 0, 1},
                    {0, 6, 999, 999, 0}
                };

     printf("The supplied input is\n");
     for(i = 1; i <= n; i++){
        for(j = 1; j<= n; j++){
            printf("%d\t", D[i][j]);
        }
        printf("\n");
    }

    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 pair shortest paths:\n");
    for(i = 1; i <= n; i++){
        for(j = 1; j<= n; j++){
            printf("%d\t", D[i][j]);
        }
        printf("\n");
    }
    return 0;
}

One thought on “Floyd’s Algorithm – C Implementation

Let me Know What you Think!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s