by: Jayson McleodPosted on

The Floyd-Warshall algorithm emerges as a powerful mechanism for determining the distances amongst every node pair within a weighted graph. It’s a strategy rooted in dynamic programming, comparable to Gauss-Jordan elimination, and is instrumental in pinpointing the most direct route connecting any two specific nodes.

In this write-up, we aim to unpack the core operational aspects of this algorithm and illustrate its real-world application using the C programming language.

Applying the Floyd-Warshall Algorithm with C

Here, we unfold an exposition of the Floyd-Warshall algorithm as articulated in C. The presented code is meticulously designed to adeptly perform computations, producing a comprehensive distance table associated with each node pair present in a weighted graph.

#include <stdlib.h>
#include <limits.h>
 
typedef struct {
    unsigned int first;
    unsigned int second;
    int weight;
} weighted_arc;

int **floyd_warshall(const weighted_arc *arcs, unsigned int size, unsigned int order)
{
    // Initialization and memory allocation
    unsigned int i, j, k;
    int **distances = malloc(order * sizeof(int *));
    
    for (i = 0; i < order; i++) {
        distances[i] = malloc(order * sizeof(int));
        for (j = 0; j < order; j++) {
            distances[i][j] = (i == j) ? 0 : INT_MAX;
        }
    }

    // Populating distances for each arc
    for (i = 0; i < size; i++) {
        distances[arcs[i].first][arcs[i].second] = arcs[i].weight;
    }

    // Calculating shortest paths
    for (k = 0; k < order; k++) {
        for (i = 0; i < order; i++) {
            for (j = 0; j < order; j++) {
                int potential_distance = distances[i][k] + distances[k][j];
                if (distances[i][k] != INT_MAX && distances[k][j] != INT_MAX 
                     && distances[i][j] > potential_distance) {
                    distances[i][j] = potential_distance;
                }
            }
        }
    }

    return distances;
}

Practical Example: Calculating the Distance Table

Now, let’s witness the Floyd-Warshall algorithm in action through a sample program. In this instance, we will compute the distance table for a graph consisting of 4 nodes and 5 arcs. 

Here’s the code:

#include <stdio.h>
#include <stdlib.h>
 
// A function to create connections between two arcs
void weighted_arc_connect(weighted_arc *arcs, unsigned int first, unsigned int second,
        int weight, unsigned int *pos)
{
    arcs[*pos].first = first;
    arcs[*pos].second = second;
    arcs[*pos].weight = weight;
    (*pos)++;
}

// A function to display the distance table
void print_distances(int **distances, unsigned int order)
{
    for (unsigned int i = 0; i < order; i++) {
        for (unsigned int j = 0; j < order; j++) {
            printf("%d ", distances[i][j]);
        }
        printf("\n");
    }
}

int main(void)
{
    // ... [rest of the code is the same]
}

// The output will display the following distance table:
// 0 -1 -2 0
// 4 0 2 4
// 5 1 0 2
// 3 -1 1 0

Conclusion

The implementation of the Floyd-Warshall algorithm in C serves as a comprehensive tool for effectively solving the shortest path problem for all node pairs. Grasping its application can prove invaluable in addressing complex graph-related challenges.

Leave a Reply