Floyd-Warshall's Algorithm: All-Pairs Shortest Path Problem

Floyd-Warshall's Algorithm

Objective:

To understand and implement the Floyd-Warshall’s algorithm for finding the shortest paths between all pairs of vertices in a weighted graph.

Introduction :

The Floyd-Warshall’s algorithm is a dynamic programming algorithm used to solve the all-pairs shortest path problem. Given a weighted graph, it finds the shortest path between every pair of vertices. The algorithm can handle graphs with both positive and negative edge weights, but it cannot handle negative cycles

Algorithm:

The Floyd-Warshall’s algorithm works by iteratively considering each vertex in the graph as a possible intermediate vertex in the shortest path between every pair of vertices.

Input:

A weighted graph G with vertices V = {1, 2, …, n} and a weight matrix W where W[i][j] is the weight of the edge from vertex i to vertex j. If there is no edge from i to j, then W[i][j] = infty. Also, W[i][i] = 0 for all i

Output:

A distance matrix D where D[i][j] is the length of the shortest path from vertex i to vertex j.

Steps:

Initialization:
- Create a distance matrix D and initialize it with the weight matrix W. That is, D[i][j] = W[i][j] for all i and j. This initialization step is crucial for setting the base case for the dynamic programming approach
Iteration:
- For each vertex k from 1 to n:
  - For each vertex i from 1 to n:
    - For each vertex j from 1 to n:
      - Update D[i][j] as follows:
        D[i][j] = min(D[i][j], D[i][k] + D[k][j])

Explanation

The outer loop iterates through each vertex k which represents a possible intermediate node in a shortest path from node i to node j.
The inner loops iterate through each possible pair of vertices i and j.
Inside the inner loops, the algorithm checks if going from vertex i to vertex j through vertex k is shorter than the current known shortest path between i and j. If it is, the shortest path is updated
By the end of the algorithm, D[i][j] will contain the shortest path distance from vertex i to vertex j for all pairs of vertices.

Assignment 6. Set B a) SPPU:

Write a c program for the implementation of Floyd Warshall’s algorithm for finding all pairs shortest path using adjacency cost matrix

#include <limits.h>

// Define the maximum number of vertices in the graph
#define V 100 // Adjust this value based on your graph size

// Function to implement the Floyd-Warshall algorithm
void floydWarshall(int graph[][V], int n) {
    int dist[V][V]; // Output matrix that will have the shortest distances

    // Step 1: Initialize the distance matrix with the input graph
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = graph[i][j];
        }
    }

    // Step 2: Iterate through all vertices and update the distance matrix
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // If vertex k is on the shortest path from i to j, update the value of dist[i][j]
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // Step 3: Print the shortest distance matrix
    printf("The shortest distance matrix:\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] == INT_MAX)
                printf("INF\t");
            else
                printf("%d\t", dist[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int n; // Number of vertices in the graph
    printf("Enter the number of vertices: ");
    scanf("%d", &n);

    int graph[V][V]; // Adjacency cost matrix

    // Input the adjacency cost matrix
    printf("Enter the adjacency cost matrix (use INF for no direct edge):\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &graph[i][j]);
            if (graph[i][j] == -1) { // Assuming -1 represents INF (no edge)
                graph[i][j] = INT_MAX;
            }
        }
    }

    // Run the Floyd-Warshall algorithm
    floydWarshall(graph, n);

    return 0;
}