Floyd Warshall Algorithm | DSA in C++ - Software Development PDF Download

Introduction

The Floyd-Warshall algorithm is a powerful graph algorithm used to find the shortest paths between all pairs of vertices in a weighted graph. It efficiently solves the All-Pairs Shortest Path problem, which is a fundamental task in graph theory. This article aims to provide a beginner-friendly explanation of the Floyd-Warshall algorithm using C++, along with multiple examples and sample problems.

Understanding the Problem

The All-Pairs Shortest Path problem involves finding the shortest path between all pairs of vertices in a graph. Each edge in the graph has a weight or cost associated with it, and the goal is to minimize the total weight of the path.

Overview of the Floyd-Warshall Algorithm

The Floyd-Warshall algorithm solves the All-Pairs Shortest Path problem by iteratively updating the distance matrix. It uses dynamic programming to build the solution incrementally.

The algorithm works as follows:

• Initialize a 2D distance matrix with the weights of the edges in the graph.
• For each vertex, consider it as an intermediate vertex in the shortest path.
• Update the distance matrix by comparing the current distance between two vertices with the sum of the distances through the intermediate vertex.
• Repeat this process for all vertices, gradually building the shortest paths between all pairs.

Implementation in C++

Let's implement the Floyd-Warshall algorithm in C++:

#include <iostream>

#include <climits>

#define V 4 // Number of vertices

void floydWarshall(int graph[V][V]) {

  int dist[V][V];

  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] != INT_MAX && dist[k][j] != INT_MAX

            && dist[i][k] + dist[k][j] < dist[i][j]) {

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

        }

      }

    }

  }

  // Print the shortest distances

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

    for (int j = 0; j < V; ++j) {

      if (dist[i][j] == INT_MAX)

        std::cout << "INF ";

      else

        std::cout << dist[i][j] << " ";

    }

    std::cout << std::endl;

  }

}

int main() {

  int graph[V][V] = {{0, 3, INT_MAX, 5},

                     {2, 0, INT_MAX, 4},

                     {INT_MAX, 1, 0, INT_MAX},

                     {INT_MAX, INT_MAX, 2, 0}};

  floydWarshall(graph);

  return 0;

}

Example: Finding Shortest Paths

Consider the following graph:

       3       5

    (0)---(3)---(2)

     |     / \     |

    2|    /   \4   |1

     |   /     \   |

    (1)---(4)---(3)

       2       2

The distance matrix after applying the Floyd-Warshall algorithm will be:

    0 3 5 5

    2 0 4 3

    3 1 0 4

    5 3 2 0

Time and Space Complexity

The time complexity of the Floyd-Warshall algorithm is O(V^3), where V is the number of vertices in the graph. The space complexity is O(V^2) for the distance matrix.

Sample Problems and Solutions

Problem 1: Given a graph with V vertices and E edges, find the shortest path between all pairs of vertices.

Apply the Floyd-Warshall algorithm to the graph.

Problem 2: Find the diameter of a graph, which is the longest shortest path between any two vertices.

After applying the Floyd-Warshall algorithm, find the maximum value in the distance matrix.

Conclusion

The Floyd-Warshall algorithm is a versatile algorithm for solving the All-Pairs Shortest Path problem efficiently. By using dynamic programming, it finds the shortest paths between all pairs of vertices in a graph. This article has provided a beginner-friendly explanation of the algorithm using C++, along with code examples and sample problems to help you understand its concepts and applications.