Floyd-Warshall Algorithm For Using Dynamic Programming

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.

Here's How to Land a Top Software Developer Job

Full Stack Developer - MERN StackExplore Program

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.

Learn the Ins & Outs of Software Development

Caltech Coding BootcampExplore Program

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.