-
Notifications
You must be signed in to change notification settings - Fork 0
/
Floyd_Warshall_Algo_DP.cpp
62 lines (51 loc) · 1.12 KB
/
Floyd_Warshall_Algo_DP.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
#define Z 99999
#define N 4
/*
Time Complexity : O(n^3)
Space Complexity : O(n*n)
*/
void printMatrix(int dp[][N])
{
for(int i=0 ; i<N ; i++)
{
for(int j=0 ; j<N ; j++)
{
if(dp[i][j] == Z)
cout<<"INF ";
else
cout<<dp[i][j]<<" ";
}
cout<<endl;
}
}
void floydWarshallDP(int graph[][N])
{
int dp[N][N];
//initializing the dp table or
//matrix with the given graph values.
for(int i=0 ; i<N ; i++)
for(int j=0 ; j<N ; j++)
dp[i][j] = graph[i][j];
//for creating k-graphs
for(int k=0 ; k<N ; k++)
//generating the matrix with two 2 loops
for(int i=0 ; i<N ; i++)
for(int j=0 ; j<N ; j++)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
cout<<"The shortest distance matrix formed is : "<<endl;
printMatrix(dp);
}
int main()
{
int graph[N][N] =
{
{ 0, 3, Z, 7 },
{ 8, 0, 2, Z },
{ 5, Z, 0, 1 },
{ 2, Z, Z, 0 }
};
floydWarshallDP(graph);
return 0;
}