# Floyd Warshall Algorithm using Dynamic Programming

This is a C++ Program to implement the Floyd Warshall Algorithm using Dynamic Programming technique.

Problem Description

Find shortest distance between each pair of vertices in the given graph. This problem is also known as All pairs shortest path problem.

Problem Solution

One solution to this problem is to apply Dijkstra algorithm for all vertices. But if the graph contain negative weight edges, Dijkstra algorithm could not be applied.

In that case, we have Floyd Warshall algorithm. We start with the adjacency matrix of the graph. If there is no path from vertex i to j, the cell(i,j) in the matrix will be initialized to INFINITY. And each cell(i,i) will be initialized to 0.

Then, we consider every vertex(one by one) as an intermediate vertex. For example – if intermediate is vertex i, and we want to reach from vertex j to vertex k, we will first go from vertex i to vertex j and then vertex j to vertex k instead of directly going from j to k.

It is O(V^3) algorithm where V is the number of vertices.

Expected Input and Output

Case-1:

```
number of vertices=8
number of edges=9

Information of all edges(source, destination, weight)
1 2 8
2 3 7
2 4 3
3 5 5
3 6 2
4 7 -4
4 8 6
5 7 -3
6 8 9

Expected Result:

The all pairs shortest distance matrix is
1     2     3     4     5     6     7     8
_______________________________________________________
1 |     0     8    15    11    20    17     7    17
2 |   INF     0     7     3    12     9    -1     9
3 |   INF   INF     0   INF     5     2     2    11
4 |   INF   INF   INF     0   INF   INF    -4     6
5 |   INF   INF   INF   INF     0   INF    -3   INF
6 |   INF   INF   INF   INF   INF     0   INF     9
7 |   INF   INF   INF   INF   INF   INF     0   INF
8 |   INF   INF   INF   INF   INF   INF   INF     0```

Case-2:

Note: Join free Sanfoundry classes at Telegram or Youtube
```
number of vertices=5
number of edges=7

Information of all edges(source, destination, weight)
1 2 3
1 4 4
2 4 5
3 1 1
3 5 8
4 2 2
4 5 6

Expected Result:

The all pairs shortest distance matrix is
1     2     3     4     5
_____________________________________
1 |     0     3   INF     4    10
2 |   INF     0   INF     5    11
3 |     1     4     0     5     8
4 |   INF     2   INF     0     6
5 |   INF   INF   INF   INF     0```

Case-3:

```
number of vertices=4
number of edges=8

Information of all edges(source, destination, weight)
1 2 8
2 3 7
3 4 6
4 1 5
1 4 4
4 3 3
3 2 2
2 1 1

Expected Result:

The all pairs shortest distance matrix is
1     2     3     4
_______________________________
1 |     0     8     7     4
2 |     1     0     7     5
3 |     3     2     0     6
4 |     5     5     3     0```
Program/Source Code

Here is source code of the C++ Program to solve All pairs shortest path problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

1. ` `
2. `//Floyd warshall algorithm`
3. `#include<bits/stdc++.h>`
4. `using namespace std;`
5. ` `
6. `int main()`
7. `{`
8. `    int i,j,k;`
9. `    int n,e;`
10. `    int s,d,w;`
11. ` `
12. `    cout<<"Enter the number of vertices ";`
13. `    cin>>n;`
14. ` `
15. `    //adjacency matrix`
16. `    //initialized to infinity`
17. `    vector<vector<int> > distMat(n,vector<int>(n,INT_MAX));`
18. ` `
19. `    for(i=0;i<n;i++)`
20. `    {`
21. `        //distance of verter i from itself is always zero`
22. `        distMat[i][i]=0;`
23. `    }`
24. ` `
25. `    cout<<"Enter the number of edges ";`
26. `    cin>>e;`
27. ` `
28. `    cout<<"Enter the src, dest and weight of each edge"<<endl;`
29. `    for(i=0;i<e;i++)`
30. `    {`
31. `        cin>>s>>d>>w;`
32. ` `
33. `        //add to the adjacency list`
34. ` `
35. `        distMat[s-1][d-1]=w;`
36. `    }`
37. ` `
38. `    //now, we have the adjacency matrix`
39. `    //we will create n matrices from this considering a vertex as an intermediate vertex`
40. ` `
41. `    //intermediate`
42. `    for(k=0;k<n;k++)`
43. `    {`
44. `        //source`
45. `        for(i=0;i<n;i++)`
46. `        {`
47. `            //destination`
48. `            for(j=0;j<n;j++)`
49. `            {`
50. `                if(distMat[i][k]!=INT_MAX && `
51. `                   distMat[k][j]!=INT_MAX &&`
52. `                   distMat[i][k]+distMat[k][j]<distMat[i][j])`
53. `                    {`
54. `                        distMat[i][j]=distMat[i][k]+distMat[k][j];`
55. `                    }`
56. ` `
57. `            }`
58. `        }`
59. `    }`
60. ` `
61. `    cout<<endl<<"The all pairs shortest distance matrix is "<<endl;`
62. ` `
63. `    cout<<"       ";`
64. ` `
65. `    for(i=0;i<n;i++)`
66. `    {`
67. `        printf("%6d",i+1);`
68. `    }`
69. ` `
70. `    cout<<endl;`
71. ` `
72. `    for(i=0;i<6*n;i++)`
73. `    {`
74. `        cout<<"_";`
75. `    }`
76. ` `
77. `    cout<<"_______"<<endl;`
78. ` `
79. `    for(i=0;i<n;i++)`
80. `    {`
81. `        printf("%5d |",i+1);`
82. `        for(j=0;j<n;j++)`
83. `        {`
84. `            if(distMat[i][j]==INT_MAX)`
85. `                printf("   INF");`
86. ` `
87. `            else`
88. `                printf("%6d",distMat[i][j]);`
89. `            //cout<<distMat[i][j]<<"   ";`
90. `        }`
91. ` `
92. `        cout<<endl;`
93. `    }`
94. ` `
95. `    return 0;`
96. `}`
Program Explanation

In the main function, we take input for number of vertices and edges in the graph. Then we will take inputs for the information of all edges(source, destination and weight). This information is stored in the adjaceny matrix. Then, the nested loop will calculate all pair shortest paths of the graph. Finally, this matrix will be displayed.

Runtime Test Cases
```
Case-1:
\$ g++ floydWarshall.cpp
\$ ./a.out
Enter the number of vertices 5 7
Enter the number of edges Enter the src, dest and weight of each edge
1 2 3
1 4 4
2 4 5
3 1 1
3 5 8
4 2 2
4 5 6

The all pairs shortest distance matrix is
1     2     3     4     5
_____________________________________
1 |     0     3   INF     4    10
2 |   INF     0   INF     5    11
3 |     1     4     0     5     8
4 |   INF     2   INF     0     6
5 |   INF   INF   INF   INF     0

Case-2:
\$ ./a.out
Enter the number of vertices 4
Enter the number of edges 8
Enter the src, dest and weight of each edge
1 2 8
2 3 7
3 4 6
4 1 5
1 4 4
4 3 3
3 2 2
2 1 1

The all pairs shortest distance matrix is
1     2     3     4
_______________________________
1 |     0     8     7     4
2 |     1     0     7     5
3 |     3     2     0     6
4 |     5     5     3     0

Case-3:
\$ ./a.out
Enter the number of vertices 8
Enter the number of edges 9
Enter the src, dest and weight of each edge
1 2 8
2 3 7
2 4 3
3 5 5
3 6 2
4 7 -4
4 8 6
5 7 -3
6 8 9

The all pairs shortest distance matrix is
1     2     3     4     5     6     7     8
_______________________________________________________
1 |     0     8    15    11    20    17     7    17
2 |   INF     0     7     3    12     9    -1     9
3 |   INF   INF     0   INF     5     2     2    11
4 |   INF   INF   INF     0   INF   INF    -4     6
5 |   INF   INF   INF   INF     0   INF    -3   INF
6 |   INF   INF   INF   INF   INF     0   INF     9
7 |   INF   INF   INF   INF   INF   INF     0   INF
8 |   INF   INF   INF   INF   INF   INF   INF     0```

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.