Floyd Warshall Algorithm in C

The Floyd-Warshall algorithm in C is a graph algorithm that finds the shortest path between two vertices in a graph in a weighted graph with positive or negative edge weights but without negative cycles. The algorithm is named after the British mathematician Floyd Warshall. The algorithm is also known as the all-pairs shortest path algorithm.

The algorithm compares all possible paths between two vertices in a graph and finds the shortest path. It does so in O(V³) time even when the graph is sparse.

In this algorithm, we will use a matrix to represent the graph. The matrix will have the following structure:

[
  [0, 1, 2, 3, 4],
  [1, 0, 5, 6, 7],
  [2, 5, 0, 8, 9],
  [3, 6, 8, 0, 10],
  [4, 7, 9, 10, 0]
]

Then, we will use the following formula to find the shortest path between two vertices:

d[i][j] = min(d[i][j], d[i][k] + d[k][j])

Example:
Fo example, if we have the following matrix:

\(\begin{bmatrix}
4 & 2 & 5 & 2\\
4 & 3 & 1 & 4\\
2 & 5 & 2 & 1\\
5 & 3 & 1 & 4
\end{bmatrix}\)

The shortest path matrix is:

\(\begin{bmatrix}
4 & 2 & 3 & 2\\
3 & 3 & 1 & 2\\
2 & 4 & 2 & 1\\
3 & 3 & 1 & 2
\end{bmatrix}\)

Problem Description

Write a C program that finds the shortest path between two vertices in a graph and prints the shortest path matrix using Floyd Warshall Algorithm.

Problem Solution

1. Ask the user to enter the edges of the graph as a matrix representation.
2. Print the original matrix.
3. Pass the matrix to the function floydWarshall to find the shortest path matrix.
4. Print the shortest path matrix.

Subscribe Now: C Algorithms Newsletter | Important Subjects Newsletters

Methods used:

void floydWarshall(int **, int) – This function will find the shortest path between two vertices in a graph using the Floyd-Warshall algorithm. The parameters are the graph represented as a matrix and the number of rows.

Program/Source Code

Here is the source code of a C Program that will find the shortest path between two vertices in a graph using the Floyd-Warshall algorithm. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * C Program to find the shortest path between two vertices in a graph

```
 * using the Floyd-Warshall algorithm
```
```
 */
```
```
 
```
```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
 
```
```
void floydWarshall(int **graph, int n)
```
```
{
```
```
    int i, j, k;
```
```
    for (k = 0; k < n; k++)
```
```
    {
```
```
        for (i = 0; i < n; i++)
```
```
        {
```
```
            for (j = 0; j < n; j++)
```
```
            {
```

                if (graph[i][j] > graph[i][k] + graph[k][j])

                    graph[i][j] = graph[i][k] + graph[k][j];

```
            }
```
```
        }
```
```
    }
```
```
}
```
```
 
```
```
int main(void)
```
```
{
```
```
    int n, i, j;
```

    printf("Enter the number of vertices: ");

```
    scanf("%d", &n);
```

    int **graph = (int **)malloc((long unsigned) n * sizeof(int *));

```
    for (i = 0; i < n; i++)
```
```
    {
```

        graph[i] = (int *)malloc((long unsigned) n * sizeof(int));

```
    }
```
```
    for (i = 0; i < n; i++)
```
```
    {
```
```
        for (j = 0; j < n; j++)
```
```
        {
```
```
            if (i == j)
```
```
                graph[i][j] = 0;
```
```
            else
```
```
                graph[i][j] = 100;
```
```
        }
```
```
    }
```
```
    printf("Enter the edges: \n");
```
```
    for (i = 0; i < n; i++)
```
```
    {
```
```
        for (j = 0; j < n; j++)
```
```
        {
```
```
            printf("[%d][%d]: ", i, j);
```
```
            scanf("%d", &graph[i][j]);
```
```
        }
```
```
    }
```
```
    printf("The original graph is:\n");
```
```
    for (i = 0; i < n; i++)
```
```
    {
```
```
        for (j = 0; j < n; j++)
```
```
        {
```
```
            printf("%d ", graph[i][j]);
```
```
        }
```
```
        printf("\n");
```
```
    }
```
```
    floydWarshall(graph, n);
```

    printf("The shortest path matrix is:\n");

```
    for (i = 0; i < n; i++)
```
```
    {
```
```
        for (j = 0; j < n; j++)
```
```
        {
```
```
            printf("%d ", graph[i][j]);
```
```
        }
```
```
        printf("\n");
```
```
    }
```
```
    return 0;
```
```
}
```

Program Explanation

1. The program begins with asking the user to input the edges of the graph and represents them as a matrix representation.
2. Pass the matrix and the number of vertices n as input to the function floydWarshall.
3. In the function, loop nest from 0 to size and inside that make another loop from 0 to size where we compare the weights respectively as seen in the program.
4. Pass the matrix to the function floydWarshall to find the shortest path matrix.
5. Print the shortest path matrix.

Time complexity: O(V³)
The time complexity of the algorithm is O(V³), where V is the number of vertices in the graph.

Space Complexity: O(V²)
The space complexity of the algorithm is O(V²), where V is the number of vertices in the graph.

Runtime Test Cases

In this case, we enter “4” as the number of vertices as input to find the shortest path between two vertices in the graph using the Floyd-Warshall algorithm.

Enter the number of vertices: 4
Enter the edges: 
[0][0]: 0
[0][1]: 12
[0][2]: 45
[0][3]: 2
[1][0]: 1
[1][1]: 0
[1][2]: 45
[1][3]: 32
[2][0]: 77
[2][1]: 43
[2][2]: 0
[2][3]: 2
[3][0]: 42
[3][1]: 3
[3][2]: 88
[3][3]: 0
The original graph is:
0 12 45 2 
1 0 45 32 
77 43 0 2 
42 3 88 0 
The shortest path matrix is:
0 5 45 2 
1 0 45 3 
6 5 0 2 
4 3 48 0

Additional Approach:

In this approach, we find the shortest distance between each pair of vertices in a given edge-weighted directed graph using the Floyd-Warshall algorithm.

Program/Source Code

Here is source code of the C Program to Implement Floyd-Warshall Algorithm. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
// Program for Floyd Warshall Algorithm
```
```
#include<stdio.h>
```
```
 
```

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

```
 
```

/* Define Infinite as a large enough value. This value will be used

 for vertices not connected to each other */

```
#define INF 99999
```
```
 
```

// A function to print the solution matrix

```
void printSolution(int dist[][V]);
```
```
 
```

// Solves the all-pairs shortest path problem using Floyd Warshall algorithm

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

    /* Initialize the solution matrix same as input graph matrix. Or

     we can say the initial values of shortest distances are based

     on shortest paths considering no intermediate vertex. */

```
    for (i = 0; i < V; i++)
```
```
        for (j = 0; j < V; j++)
```
```
            dist[i][j] = graph[i][j];
```
```
 
```
```
    for (k = 0; k < V; k++)
```
```
    {
```

        // Pick all vertices as source one by one

```
        for (i = 0; i < V; i++)
```
```
        {
```

            // Pick all vertices as destination for the

```
            // above picked source
```
```
            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];

```
            }
```
```
        }
```
```
    }
```
```
 
```

    // Print the shortest distance matrix

```
    printSolution(dist);
```
```
}
```
```
 
```

/* A utility function to print solution */

```
void printSolution(int dist[][V])
```
```
{
```

    printf("Following matrix shows the shortest distances"

        " between every pair of vertices \n");

```
    int i, j;
```
```
    for (i = 0; i < V; i++)
```
```
    {
```
```
        for (j = 0; j < V; j++)
```
```
        {
```
```
            if (dist[i][j] == INF)
```
```
                printf("%7s", "INF");
```
```
            else
```

                printf("%7d", dist[i][j]);

```
        }
```
```
        printf("\n");
```
```
    }
```
```
}
```
```
 
```

// driver program to test above function

```
int main()
```
```
{
```

    /* Let us create the following weighted graph

```
    10
```
```
    (0)------->(3)
```
```
     |         /|\
```
```
   5 |          |
```
```
     |          | 1
```
```
    \|/         |
```
```
    (1)------->(2)
```
```
     3           */
```

    int graph[V][V] = { { 0, 5, INF, 10 },

                        { INF, 0, 3, INF },

                        { INF, INF, 0, 1 },

                        { INF, INF, INF, 0 }

```
                      };
```
```
 
```
```
    // Print the solution
```
```
    floydWarshell(graph);
```
```
    return 0;
```
```
}
```

Program Explanation

1. Define number of vertices in the graph.
2. Define Infinite as a large enough value. This value will be used for the vertices that are not connected to each other.
3. dist[][] will be the output matrix that will finally have the shortest distance between every pair of vertices.
4. Initialize the solution matrix same as input graph matrix.
5. Add all vertices one by one to the set of intermediate vertices.
6. Before beginning an iteration, we have shortest distances between all pairs of vertices such that the shortest distances consider just the vertices in set {0, 1, 2,… k-1} as intermediate vertices.
7. After the end of a iteration, vertex no. k is added to the set of intermediate vertices and the set becomes {0, 1, 2, .. k}
8. Pick all vertices as source one by one and if vertex k is on the shortest path from i to j, then update the value of dist[i][j].
9. Print the shortest distance matrix.

Runtime Test Cases

Here is the result to find the shortest distance between each pair of vertices using Floyd-Warshall algorithm.

 
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

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.

« Prev - Postorder Traversal of a Binary Tree without using Recursion in C

» Next - BFS Program in C

Related Posts:

Recommended Articles: