forked from D3v3sh5ingh/Graph-Theory-Algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Q6Floydd.cpp
60 lines (51 loc) · 1.32 KB
/
Q6Floydd.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
#include <bits/stdc++.h>
using namespace std;
#define nV 4
#define INF 9999
void printMatrix(int matrix[][nV]);
// Implementing floyd warshall algorithm
void floydWarshall(int graph[][nV])
{
int matrix[nV][nV], i, j, k;
for (i = 0; i < nV; i++)
for (j = 0; j < nV; j++)
matrix[i][j] = graph[i][j];
for (k = 0; k < nV; k++)
{
for (i = 0; i < nV; i++)
{
for (j = 0; j < nV; j++)
{
if (matrix[i][k] + matrix[k][j] < matrix[i][j])
matrix[i][j] = matrix[i][k] + matrix[k][j];
}
}
}
printMatrix(matrix);
}
void printMatrix(int matrix[][nV])
{
for (int i = 0; i < nV; i++)
{
for (int j = 0; j < nV; j++)
{
if (matrix[i][j] == INF)
printf("%4s", "INF");
else
printf("%4d", matrix[i][j]);
}
printf("\n");
}
}
int main()
{
int graph[nV][nV] = {{0, 3, INF, 5},
{2, 0, INF, 4},
{INF, 1, 0, INF},
{INF, INF, 2, 0}};
cout << "Original given graph costs" << endl;
printMatrix(graph);
cout << endl
<< "Applying floyd warshall" << endl;
floydWarshall(graph);
}