Dynamic Programming is a technique for breaking down a big problem into smaller chunks and finding an effective solution. The perfect answer to each of the smaller subproblems determines the best solution to the core problem. Richard Bellman introduced the idea for the technique in the 1950s. The DP method computes the answer once for each subproblem, saving time by not recalculating it when the same subproblem arises again.
As you finish with the tutorial, you will better understand the dynamic programming approach to the Floyd Warshal Algorithm with all the necessary details and practical implementations.
What Is the Floyd Warshall Algorithm?
The Floyd Warshall Algorithm is used to calculate the shortest path between two pairs of numbers. The goal is to discover the shortest distance between each pair of vertices in an edge-weighted directed Graph.
Now, look at the Floyd Warshall algorithm to solve the all-pair shortest problem.
What Is the Solution to the All Pair Shortest Path Problem Using the Floyd Warshall Algorithm?
You use Dynamic programming to solve the problem using the Floyd Warshall algorithm,
- Firstly, you set the solution matrix to the same value as the input graph matrix.
- The solution matrix is then updated by treating all vertices as an intermediate vertex.
- The goal is to choose all vertices one by one and update all shortest routes that involve the picked vertex as an intermediate vertex.
And this is the solution to solve this problem using the Floyd Warshall algorithm. Now you will implement this solution through C++ code.
How Do You Implement the Solution of the All Pair Shortest Path Problem Using Floyd Warshall Algorithm?
You will be given a graph with four vertices. Finding the shortest path between each pair, the code below will return another graph with elements indicating the shortest distance between corresponding vertices.
Code:
//A C++ Program to demonstrate Floyd Warshall Algorithm
#include <bits/stdc++.h>
using namespace std;
//We will define the number of vertices in the graph
#define Vtx 4
// We will Define Infinite as a significant enough
value.
#define INF 99999
// A function declaration to print the solution matrix
void print_sol(int distance[][Vtx]);
// A function to Solve the all-pairs shortest path problem
void floydWarshall(int graph[][Vtx])
{
/*The output matrix will be a 2D array distance[][],
which will have the shortest distance
between every pair of vertices. */
int distance[Vtx][Vtx], i, j, k;
/* Initialize the solution matrix same
as input graph matrix. Or we can say
the initial values of shortest distances
are based on shortest paths considering
no intermediate vertex. */
for (i = 0; i < Vtx; i++)
for (j = 0; j < Vtx; j++)
distance[i][j] = graph[i][j];
/* All vertices are added to the
set of intermediate vertices one by one.
--> We know shortest distances between
all pairs of vertices before we start an iteration,
and the shortest distances only consider
the vertices in set 0 through k-1 as intermediate vertices.
--> After each iteration, vertex no. k is
added to the set of intermediate vertices,
resulting in a set of 0 to k.*/
for (k = 0; k < Vtx; k++) {
// We will one by one pick all vertices as source
for (i = 0; i < Vtx; i++) {
//We will Pick all the vertices as destination
//for the above picked source
for (j = 0; j < Vtx; j++) {
//If k is located on the shortest path from I to j,
//then we update distance[i][j].
if (distance[i][j] > (distance[i][k] + distance[k][j])
&& (distance[k][j] != INF
&& distance[i][k] != INF))
distance[i][j] = distance[i][k] + distance[k][j];
}
}
}
//We will now Print the shortest distance matrix
print_sol(distance);
}
/* A function to print the solution */
void print_sol(int distance[][Vtx])
{
cout << "The following matrix shows the shortest "
"distances"
" between every pair of vertices \n";
for (int i = 0; i < Vtx; i++) {
for (int j = 0; j < Vtx; j++) {
if (distance[i][j] == INF)
cout << "INF"
<< " ";
else
cout << distance[i][j] << " ";
}
cout << endl;
}
}
int main()
{
/* Let us create the following weighted graph
10
(0)------->(3)
| /|\
5| |
| |1
\|/ |
(1)------->(2)
3
*/
int graph[Vtx][Vtx] = { { 0, 5, INF, 10 },
{ INF, 0, 3, INF },
{ INF, INF, 0, 1 },
{ INF, INF, INF, 0 } };
// Print the solution
floydWarshall(graph);
return 0;
}
This brings you to the conclusion of this tutorial. You'll now consider what your following actions might be in solving dynamic programming problems.
Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!
Next Steps
Your next stop in mastering dynamic programming problems should be Longest Common Substring. Given two strings, you must find the longest substring that is common between the two strings. You use a dynamic programming approach to maximize efficiency.
You've come to the right place if you're seeking a deeper understanding of software development that will help you carve out a successful career in the field. If this is the case, Simplilearn's Software Development Courses, which are offered in collaboration with Caltech CTME and IIT-Kanpur, may be of interest to you. These classes will teach you how to understand Data Structures, beginning with the fundamentals and progressing to more complex concepts such as Competitive Programming. This course will teach you about various data structures such as trees, graphs, queues, and so on, and will equip you to work as a software developer.
Please leave any questions or queries in the comments section below if you have any about this "Floyd Warshall Algorithm" tutorial. Our knowledgeable team will examine them and answer as quickly as possible.
