Floyd Warshall All Pairs Shortest Path in DSA C - Build from Scratch

Floyd Warshall All Pairs Shortest Path

📖 Scenario: You are working with a network of cities connected by roads. Each road has a travel cost. You want to find the shortest travel cost between every pair of cities.

🎯 Goal: Build a program that uses the Floyd Warshall algorithm to find the shortest paths between all pairs of cities in a given network.

📋 What You'll Learn

Create a 2D array called graph representing the travel costs between 4 cities.

Create an integer variable V for the number of cities.

Implement the Floyd Warshall algorithm using nested loops with variables k, i, and j.

Print the final shortest path matrix after running the algorithm.

💡 Why This Matters

🌍 Real World

Finding shortest travel costs between all pairs of cities helps in planning efficient routes for delivery, travel, or communication networks.

💼 Career

Understanding Floyd Warshall algorithm is useful for software engineers working on network routing, map services, and optimization problems.

1

Create the graph matrix

Create a 2D integer array called graph with 4 rows and 4 columns. Initialize it with these exact values: { {0, 5, 999, 10}, {999, 0, 3, 999}, {999, 999, 0, 1}, {999, 999, 999, 0} }. Also create an integer variable V and set it to 4.

DSA C

# Create the graph matrix and variable V
// Your code here

Hint

Use a 2D array to represent the graph. Use 999 to represent no direct path.

2

Set up the distance matrix

Create a 2D integer array called dist with 4 rows and 4 columns. Copy the values from graph into dist using nested for loops with variables i and j.

DSA C

#include 

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

    int dist[4][4];
    // Copy graph to dist
    // Your code here

    return 0;
}

Hint

Use two nested loops to copy each element from graph to dist.

3

Implement the Floyd Warshall algorithm

Use three nested for loops with variables k, i, and j to update dist[i][j] with the minimum of its current value and the sum of dist[i][k] and dist[k][j].

DSA C

#include 

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

    int dist[4][4];
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            dist[i][j] = graph[i][j];
        }
    }

    // Update dist using Floyd Warshall
    // Your code here

    return 0;
}

Hint

Use three nested loops to check if going through city k gives a shorter path from i to j.

4

Print the shortest path matrix

Use nested for loops with variables i and j to print the dist matrix. Print each value followed by a space. Print a new line after each row. If the value is 999, print INF instead.

DSA C

#include 

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

    int dist[4][4];
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            dist[i][j] = graph[i][j];
        }
    }

    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // Print the shortest path matrix
    // Your code here

    return 0;
}

Hint

Print each row of the dist matrix. Replace 999 with INF to show no path.