C Program to Implement Floyd-Warshall Algorithm

1. Introduction

The Floyd-Warshall algorithm is a dynamic programming technique used to solve the all-pairs shortest path problem. The problem is to find the shortest distances between every pair of vertices in a given edge-weighted directed graph. This algorithm works for both positive and negative weights.

2. Program Overview

In this program, we will:

1. Implement the Floyd-Warshall algorithm.

2. Calculate the shortest distance between every pair of vertices in the provided graph.

3. Code Program

#include<stdio.h>

// Number of vertices in the graph
#define V 4

// A function to print the solution matrix
void printSolution(int dist[][V]);

void floydWarshall (int graph[][V])
{
    int dist[V][V], i, j, k;

    // Initialize the solution matrix same as input graph matrix.
    for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
            dist[i][j] = graph[i][j];

    // Update the solution matrix by picking all vertices one by one
    for (k = 0; k < V; k++)
    {
        for (i = 0; i < V; i++)
        {
            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];
            }
        }
    }

    printSolution(dist);
}

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] == 9999)
                printf("%7s", "INF");
            else
                printf ("%7d", dist[i][j]);
        }
        printf("\n");
    }
}

int main()
{
    int graph[V][V] = { {0, 5, 9999, 10},
                        {9999, 0, 3, 9999},
                        {9999, 9999, 0, 1},
                        {9999, 9999, 9999, 0}
                      };

    floydWarshall(graph);
    return 0;
}

Output:

Following matrix shows the shortest distances between every pair of vertices
      0      5      8      9
   INF      0      3      4
   INF    INF      0      1
   INF    INF    INF      0

4. Step By Step Explanation

1. The algorithm works by repeatedly exploring paths between every pair using all possible intermediate vertices.

2. We start by creating a dist matrix and initialize it the same as the input graph matrix.

3. We then update the solution matrix by considering each vertex and updating all shortest paths which include the picked vertex as an intermediate vertex.

4. After the main procedure, we print the distance matrix. Note that the value 9999 in the program is considered as "INFINITY", i.e., a path between these vertices doesn't exist.

The algorithm uses a triple nested loop that iterates through each combination of vertices. Its time complexity is O(V^3), where V is the number of vertices in the graph.