Find the shortest path between any two nodes using the Floyd-Warshal algorithm

C There is a macro, which is defined as a piece of code or an expected value, and it will be reused whenever the user needs it. The Floyd-Walshall algorithm is the process of finding the shortest path between all pairs of vertices in a given weighted graph. The algorithm follows a dynamic programming approach to find the minimum weight graph.

Let us understand the meaning of Freud-Walschal algorithm through diagrams -

Taking vertex 1 as the source and vertex 4 as the destination, find the shortest path between them.

We have seen that there are two paths that can be connected to target vertex 4.

• 1 -> 4 – The edge has a weight of 5

• 1 -> 8 -> 3 -> 4 – The edge weight (1 2 1) is 4.

In the given graph I, we see the smallest edge connecting two vertices. So here the path between vertex 8 and vertex 3 connecting vertex 1 to vertex 4 and the edge is 4. On the other hand, there is a directed edge between vertex 1 and vertex 4, and the edge weight is 5.

Now we compare two weights, namely 4 and 5. Therefore, here 4 is the minimum weight of the graph calculated according to the Floyd Warshall algorithm.

In this article, we will use Floyd Warshall algorithm to find the shortest path between any two given nodes.

grammar

The following syntax is used in the program -

data_type[][] array_name;

parameter

data_type[][] - The data type mentioned by the user. The first array represents rows and the second array represents columns. So, this represents a two-dimensional array.

array_name - The name given to the array.

algorithm

• We will start the program with the header file 'iostream' and define the macro position as 'INF' (infinity) because later it will satisfy the two-dimensional Array matrices and if-else statements.

• Next, we create a global function definition named 'printPath' and accepts three parameters, namely 'parent[]', 'i' and 'j' Verify that the path exists.

• Then we start the main function and store the value ‘4’ into the variable ‘V’, which represents the number of vertices. Second, store the value in the form of an adjacency matrix into the variable 'dist[V][V]'. As we know, dist[i][j] represents a 2D matrix, which defines the weight of the edge from 'i' to 'j', By storing the adjacency matrix.

• Next, we are initializing the 2D array for the variable 'parent', and the size is [V][V].

In this variable we use to display each pair of vertices 'i' and 'j' w.r.t 'parent[i][j]'< /b> .

• By using two nested for loops, we will find the shortest path. The first for loop iterates over the rows in the matrix. Then, iterate over the columns in the matrix through the second for loop and then we will check the following condition using if-else statement -

• If (dist[i][j] != INF && i != j) { The Chinese translation of parent[i][j] = i;}

  is: parent[i][j] = i;}

  In the if statement, we use the 'and' (&&) operator to express two conditions. If both conditions are met, then 'i' will be stored in 'parent[i ][j]', thereby verifying that the path exists.

• other{ The Chinese translation of parent[i][j] = -1;}

  is: parent[i][j] = -1;}

  In the else statement, we initialize "-1" to "parent[i][j]" to verify that the path does not exist.

• Now we start with three nested for loops and apply k vertices in the range 0 to V-1, with the help of this range, our shortest distance and the path will be updated. In the third nested loop we use the following condition like

if (dist[i][j] < dist[i][k] + dist[k][j]){
   dist[i][j] = dist[i][k] + dist[k][j]; 
   parent[i][j] = parent[k][j];	
}

#include <iostream> 
using namespace std; 
#define INF 1000000000 // Infinity

void printPath(int parent[], int i, int j) {
   if (i == j) 
      cout << i << " "; 
   else if (parent[j] == -1) 
     cout << "No path exists"; 
   else
   { 
      printPath(parent, i, parent[j]); 
      cout << j << " "; 
   }
} 

int main() 
{
   int V = 4; 
   // V represent number of vertices
   int dist[V][V] = {{0, 2, INF, 4}, 
      {6, 0, 5, 3}, 
      {INF, 10, 0, 1}, 
      {7, 9, 8, 0}}; 
   // Represent the graph using adjacency matrix

   // Apply the Floyd Warshall algorithm to find the shortest paths
   int parent[V][V];
   for (int i = 0; i < V; i++) 
   { 
      for (int j = 0; j < V; j++) 
      {
         if (dist[i][j] != INF && i != j)
         parent[i][j] = i;
         else
         parent[i][j] = -1;
      }
   }
   // update the path and distance using the k vertex range from 0 to V-1.
   for (int k = 0; k < V; k++) 
   { 
      for (int i = 0; i < V; i++) 
      { 
         for (int j = 0; j < V; j++) 
         { 
            if (dist[i][j] > dist[i][k] + dist[k][j]) 
            {
               dist[i][j] = dist[i][k] + dist[k][j];
               parent[i][j] = parent[k][j];	
            }
         }
      }
   }

   // Print shortest distances and paths between all pairs of vertices
   for (int i = 0; i < V; i++) 
   { 
      for (int j = 0; j < V; j++) 
      { 
         cout << "The Shortest distance between " << i << " and " << j << " is ";
         if (dist[i][j] == INF) 
            cout << "INF "; 
         else
            cout << dist[i][j] << " ";

         cout << "and the shortest path is:- ";
         printPath(parent[i], i, j);
         cout << endl;
      } 
   } 

   return 0; 
}

The Shortest distance between 0 and 0 is 0 and the shortest path is:- 0 
The Shortest distance between 0 and 1 is 2 and the shortest path is:- 0 1 
The Shortest distance between 0 and 2 is 7 and the shortest path is:- 0 1 2 
The Shortest distance between 0 and 3 is 4 and the shortest path is:- 0 3 
The Shortest distance between 1 and 0 is 6 and the shortest path is:- 1 0 
The Shortest distance between 1 and 1 is 0 and the shortest path is:- 1 
The Shortest distance between 1 and 2 is 5 and the shortest path is:- 1 2 
The Shortest distance between 1 and 3 is 3 and the shortest path is:- 1 3 
The Shortest distance between 2 and 0 is 8 and the shortest path is:- 2 3 0 
The Shortest distance between 2 and 1 is 10 and the shortest path is:- 2 1 
The Shortest distance between 2 and 2 is 0 and the shortest path is:- 2 
The Shortest distance between 2 and 3 is 1 and the shortest path is:- 2 3 
The Shortest distance between 3 and 0 is 7 and the shortest path is:- 3 0 
The Shortest distance between 3 and 1 is 9 and the shortest path is:- 3 1 
The Shortest distance between 3 and 2 is 8 and the shortest path is:- 3 2 
The Shortest distance between 3 and 3 is 0 and the shortest path is:- 3