Floyd Warshall algorithm and it's applications.

The floyd warshall algorithm is for solving the All Pairs Shortest Path problem. The problem is to find shortest distances between every pair of vertices in a given edge weighted directed Graph.

INPUT :

Input will be a distance matrix (let say dis) , where dis[i][j] will represent the distance between the ith and jth node in the graph.

and you have to input 2 nodes (a and b) between whom you want to find the shortest distance .

OUTPUT:

Output will be the shortest distance between the two node a and b. and it will also output the path between the two node through which you can achieve the shortest distance.

......................................................................................................................................................................

#include<bits/stdc++.h>
using namespace std;
#define inf 1000

void iter(int dis[][5],int seq[][5],int k)
{
    for(int i=0;i<5;i++)
    {
        for(int j=0;j<5;j++)
        {
            if(i<j && i!=k && j!=k)
            {
                if(dis[i][k] + dis[k][j] < dis[i][j])
                {
                    dis[i][j] = dis[i][k] + dis[k][j];
                    dis[j][i] = dis[i][k] + dis[k][j];
                    seq[i][j] = k;
                    seq[j][i] = k;
                }
            }
        }
    }
}

void print(int a[][5])
{
    for(int i=0;i<5;i++)
    {
        for(int j=0;j<5;j++)
        {
            cout<<a[i][j]<<" ";
        }
        cout<<endl<<endl;
    }
}

void path(int a,int b,int seq[][5])
{
int k = b;
queue<int> p;
p.push(a);
do{
        int m = p.front();
        if(m == k)
        {
            cout<<m;
            p.pop();
        }
        if(seq[m][b] == b)
        {
            p.push(b);
            cout<<p.front()<<"->";
            p.pop();
            b = k;
        }
        else
        {
            if(seq[m][b] != k)
            {    
                b = seq[m][b];
             }
        }
    }while(p.empty() == false);
}

int main(void)
{
    int n,a,b;
    cout<<"enter the number of vertices in the graph"<<endl;
    cin>>n;
    int dis[5][5],seq[5][5];
    cout<<"enter the graph matrix enter -1 for self loop and edgesum + 1 or 999   for no edge"<<endl;

for(int i=0;i<5;i++)
{
    for(int j=0;j<5;j++)
    {
        cin>>dis[i][j];
    }
}

for(int i=0;i<5;i++)
{
    for(int j=0;j<5;j++)
    {
        if(i==j)
        {
            seq[i][j] = -1;
        }
        else
        {
            seq[i][j] = j;
        }
    }
}

print(seq);
cout<<endl;
print(dis);
cout<<endl;

for(int i=0;i<5;i++)
{
    iter(dis,seq,i);
}

int k;
do{
       cout<<"Enter a and b"<<endl;
       cin>>a>>b;
       cout<<"shortest distance is:"<<dis[a][b]<<" and the path is:";
       cout<<endl;
       path(a,b,seq);
       cout<<endl;
       cout<<"enter 1 to exit and any other number to continue"<<endl;
       cin>>k;
    }while(k!=1);
return 0;
}

...........................................................................................................................................................................

OUTPUT

enter the number of vertices in the graph
5
enter the graph matrix enter -1 for self loop and edgesum + 1 or 999 for no edge
-1 8 6 99 1
8 -1 7 99 99
6 7 -1 1 99
99 99 1 -1 1
1 99 99 1 -1

-1 1 2 3 4
0 -1 2 3 4
0 1 -1 3 4
0 1 2 -1 4
0 1 2 3 -1

-1 8 6 99 1
8 -1 7 99 99
6 7 -1 1 99
99 99 1 -1 1
1 99 99 1 -1

Enter a and b
0 2
shortest distance is:3 and the path is:
0->4->3->2
enter 1 to exit and any other number to continue
1

.........................................................................................................................................................................

The above code is the implementation of this youtube video https://www.youtube.com /watch?v=oNI0rf2P9gE.

the floyd algorithm can have several applications like if want to go from a place a to a place b and there are several ways to do so then the above algorithm and code will help you to find the path that will lead you to cover the minimum distance in doing so and will also save your time.