Floyd-Warshall Algorithm and its Implementation

Board Infinity
Board Infinity
Floyd-Warshall Algorithm and its Implementation

    Advanced Algorithms and Problem Solving Techniques

    How To Start Competitive Programming - A Complete Guide

    A Quick Guide to Breadth-First Search

    Depth First Search (DFS) with Explanation and Code

    Difference Between BFS and DFS (with code and diagrams)

    How to Perform Level Order Traversal?

    A Quick Guide to Backtracking Algorithm

    Solving N Queens Problem using Backtracking

    Quick Guide to Divide and Conquer Algorithm

    Longest Increasing Subsequence Problem

    Quick Note - Greedy Programming v/s Dynamic Programming

    Coin Change Problem: DP and Recursion Approach

    A Definitive Guide to Knapsack Problem

    How to Solve Subset Sum Problem?

    Understanding Huffman Coding in detail

    Understand the working of KMP Algorithm

    Longest Common Substring Problem

    Longest Common Subsequence problem: solved

    A Quick Guide to Manacher's Algorithm

    Learning About Bipartite Graphs

    Graph Coloring Problem: Explained

    Detect Cycle in Direct Graph

    Directed Acyclic Graph: Representation

    Prim's Algorithm: Explanation, Code, and Applications

    Working of Kruskal's Algorithm

    Prims and Kruskal algorithm for Maximum Spanning Tree

    Bellman Ford Algorithm in detail with code

    Floyd-Warshall Algorithm and its Implementation

    Understand Travelling Salesman Problem

    Branch And Bound Algorithm: Explained

    How to Evaluate Postfix Expression

    Introduction to Round-Robin Scheduling

    Disjoint set (Union find Algorithm)

    State Space Reduction in Algorithms

    Apriori Algorithm

    What is A* Search Algorithm?


Introduction

In this article, you will learn how floyd-warshall algorithm works. We also present C++ implementation and examples to help you understand it in a lucid manner.

A weighted graph's Floyd-Warshall method is used to determine the shortest route between all of the vertex pairs. Both the directed and undirected weighted graphs may be solved using this approach. However, it is ineffective for graphs with negative cycles (where the sum of the edges in a cycle is negative). A weighted graph is one in which each edge is assigned a numerical value. Floyd's algorithm, Roy-Floyd algorithm, Roy-Warhshall algorithm, or WFI algorithm are other names for the Floyd-Warhshall algorithm.

Implementation

For a graph with N vertices:

  1. Set Infinity as the initial value for the shortest pathways between any two vertices.
  2. In order to reach a state where all N vertices are utilized as intermediate nodes, determine the shortest routes between all pairs of vertices that employ 0 intermediate vertices, 1 intermediate vertice, and so on.
  3. Reduce any two pairs' shortest routes from the preceding procedure.
  4. The shortest path will be: min(dist[i][k]+dist[k][j],dist[i][j]), therefore for each two vertices (i,j), one should really reduce the distances between this pair using the first K nodes. The shortest path that only passes through the first K vertices is represented by dist[i][k], while the shortest path between two vertices is represented by dist[k][j]. The concatenation of the shortest paths from I to k and then from k to j will result in the shortest path.

for(int k = 1; k <= n; k++){
   for(int i = 1; i <= n; i++){
       for(int j = 1; j <= n; j++){
           dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] );
       }
   }
}


Code

#include <iostream>
using namespace std;

#define nV 4
#define INF 999

void printMatrix(int matrix[][nV]);

void floydWarshall(int graph[][nV]) {
  int matrix[nV][nV], i, j, k;

  for (i = 0; i < nV; i++)
    for (j = 0; j < nV; j++)
      matrix[i][j] = graph[i][j];

  for (k = 0; k < nV; k++) {
    for (i = 0; i < nV; i++) {
      for (j = 0; j < nV; j++) {
        if (matrix[i][k] + matrix[k][j] < matrix[i][j])
          matrix[i][j] = matrix[i][k] + matrix[k][j];
      }
    }
  }
  printMatrix(matrix);
}

void printMatrix(int matrix[][nV]) {
  for (int i = 0; i < nV; i++) {
    for (int j = 0; j < nV; j++) {
      if (matrix[i][j] == INF)
        printf("%4s", "INF");
      else
        printf("%4d", matrix[i][j]);
    }
    printf("\n");
  }
}

int main() {
  int graph[nV][nV] = {{0, 3, INF, 5},
             {2, 0, INF, 4},
             {INF, 1, 0, INF},
             {INF, INF, 2, 0}};
  floydWarshall(graph);
}

write your code here: Coding Playground

Complexity Analysis

Three loops are present. The complexity of each loop never changes. Consequently, the Floyd-Warshall algorithm's time complexity is O (n3).

The Floyd-Warshall algorithm's space complexity is O (n2).

Applications:

  1. In a directed graph, the shortest path is determined using this Algorithm.
  2. To locate directed graphs' transitive closure.
  3. To determine real matrices' inversion.
  4. To determine if a bipartite undirected graph exists