8000 Merge pull request #1156 from VAR-solutions/master · glitches-coder/Algorithms@5a07a6e · GitHub
[go: up one dir, main page]
Skip to content

Commit 5a07a6e

Browse files
i-vishii-vishi
authored
Merge pull request VAR-solutions#1156 from VAR-solutions/master
Dev updated
2 parents 861e65f + e0843ae commit 5a07a6e

File tree

1 file changed

+89
-0
lines changed

1 file changed

+89
-0
lines changed

‎Graphs/Floyd/Cplusplus/floydWarshall.cpp

Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
#include <stdio.h>
2+
#include <limits.h>
3+
using namespace std;
4+
#define dir true
5+
#define n_dir false
6+
class grafo{
7+
private:
8+
struct head_graph{
9+
int **matriz_ad;
10+
int numvert;
11+
int numares;
12+
bool direct;
13+
};
14+
bool criado = false;
15+
head_graph g;
16+
public:
17+
void create_graph(int tmax, bool tipo){
18+
g.matriz_ad = new int*[tmax];
19+
for(int i = 0; i < tmax; i++){
20+
g.matriz_ad[i] = new int[tmax];
21+
}
22+
g.numares = 0;
23+
g.numvert = tmax;
24+
g.direct = tipo;
25+
criado = true;
26+
for(int i = 0; i <tmax; i++){
27+
for(int j = 0; j<tmax; j++){
28+
if(i != j){
29+
g.matriz_ad[i][j] = INT_MAX;
30+
}
31+
else{
32+
g.matriz_ad[i][j] = 0;
33+
}
34+
}
35+
}
36+
}
37+
38+
void floyd_warshall(){
39+
for(int k = 0; k < g.numvert; k++){
40+
for(int i = 0; i < g.numvert; i++){
41+
for(int j = 0; j <g.numvert; j++){
42+
if((g.matriz_ad[i][k]!= INT_MAX)
43+
&&(g.matriz_ad[k][j] != INT_MAX)
44+
&&(g.matriz_ad[i][j] > g.matriz_ad[i][k] +g.matriz_ad[k][j])){
45+
g.matriz_ad[i][j] = g.matriz_ad[i][k] +g.matriz_ad[k][j];
46+
}
47+
}
48+
}
49+
}
50+
}
51+
52+
void add_edge(int u, int v, int peso){
53+
if(criado){
54+
g.numares++;
55+
g.matriz_ad[u][v] = peso;
56+
if(!g.direct){
57+
g.matriz_ad[v][u] = peso;
58+
}
59+
}
60+
}
61+
62+
void matriz_ad(){
63+
for(int i = 0; i < g.numvert; i++){
64+
for(int j = 0; j< g.numvert; j++){
65+
if(g.matriz_ad[i][j] == INT_MAX){
66+
printf("I ");
67+
}else{
68+
printf("%d ", g.matriz_ad[i][j]);
69+
}
70+
}
71+
printf("\n");
72+
}
73+
}
74+
};
75+
int main(){
76+
grafo g;
77+
g.create_graph(4,dir);
78+
g.add_edge(1,0,2);
79+
g.add_edge(0,2,3);
80+
g.add_edge(2,3,1);
81+
g.add_edge(3,0,6);
82+
g.add_edge(2,1,7);
83+
printf("initial matriz of adjacency(I is infinity)\n");
84+
g.matriz_ad();
85+
g.floyd_warshall();
86+
printf("end matriz of adjacency\n");
87+
g.matriz_ad();
88+
return 0;
89+
}

0 commit comments

Comments
 (0)
0