FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
Java/DataStructures/Graphs/FloydWarshall.java at master · primary-code-test/Java · GitHub
primary-code-test
Java
Repository navigation
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
Java
/
DataStructures
/
Graphs
/
FloydWarshall.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
77 lines (72 loc) · 3.08 KB
Breadcrumbs
Java
/
DataStructures
/
Graphs
/
FloydWarshall.java
Copy path
File metadata and controls
77 lines (72 loc) · 3.08 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
package
DataStructures
.
Graphs
;
import
java
.
util
.
Arrays
;
import
java
.
util
.
Scanner
;
public
class
FloydWarshall
{
private
int
DistanceMatrix
[][];
private
int
numberofvertices
;
// number of vertices in the graph
public
static
final
int
INFINITY
=
999
;
public
FloydWarshall
(
int
numberofvertices
) {
DistanceMatrix
=
new
int
[
numberofvertices
+
1
]
[
numberofvertices
+
1
];
// stores the value of distance from all the possible path form the source
// vertex to destination vertex
Arrays
.
fill
(
DistanceMatrix
,
0
);
this
.
numberofvertices
=
numberofvertices
;
}
public
void
floydwarshall
(
int
AdjacencyMatrix
[][])
// calculates all the distances from source to destination vertex
{
for
(
int
source
=
1
;
source
<=
numberofvertices
;
source
++) {
for
(
int
destination
=
1
;
destination
<=
numberofvertices
;
destination
++) {
DistanceMatrix
[
source
][
destination
] =
AdjacencyMatrix
[
source
][
destination
];
}
}
for
(
int
intermediate
=
1
;
intermediate
<=
numberofvertices
;
intermediate
++) {
for
(
int
source
=
1
;
source
<=
numberofvertices
;
source
++) {
for
(
int
destination
=
1
;
destination
<=
numberofvertices
;
destination
++) {
if
(
DistanceMatrix
[
source
][
intermediate
] +
DistanceMatrix
[
intermediate
][
destination
]
<
DistanceMatrix
[
source
][
destination
])
// if the new distance calculated is less then the earlier shortest
// calculated distance it get replaced as new shortest distance
{
DistanceMatrix
[
source
][
destination
] =
DistanceMatrix
[
source
][
intermediate
] +
DistanceMatrix
[
intermediate
][
destination
];
}
}
}
}
for
(
int
source
=
1
;
source
<=
numberofvertices
;
source
++)
System
.
out
.
print
(
"
\t
"
+
source
);
System
.
out
.
println
();
for
(
int
source
=
1
;
source
<=
numberofvertices
;
source
++) {
System
.
out
.
print
(
source
+
"
\t
"
);
for
(
int
destination
=
1
;
destination
<=
numberofvertices
;
destination
++) {
System
.
out
.
print
(
DistanceMatrix
[
source
][
destination
] +
"
\t
"
);
}
System
.
out
.
println
();
}
}
public
static
void
main
(
String
...
arg
) {
Scanner
scan
=
new
Scanner
(
System
.
in
);
System
.
out
.
println
(
"Enter the number of vertices"
);
int
numberOfVertices
=
scan
.
nextInt
();
int
[][]
adjacencyMatrix
=
new
int
[
numberOfVertices
+
1
][
numberOfVertices
+
1
];
System
.
out
.
println
(
"Enter the Weighted Matrix for the graph"
);
for
(
int
source
=
1
;
source
<=
numberOfVertices
;
source
++) {
for
(
int
destination
=
1
;
destination
<=
numberOfVertices
;
destination
++) {
adjacencyMatrix
[
source
][
destination
] =
scan
.
nextInt
();
if
(
source
==
destination
) {
adjacencyMatrix
[
source
][
destination
] =
0
;
continue
;
}
if
(
adjacencyMatrix
[
source
][
destination
] ==
0
) {
adjacencyMatrix
[
source
][
destination
] =
INFINITY
;
}
}
}
System
.
out
.
println
(
"The Transitive Closure of the Graph"
);
FloydWarshall
floydwarshall
=
new
FloydWarshall
(
numberOfVertices
);
floydwarshall
.
floydwarshall
(
adjacencyMatrix
);
scan
.
close
();
}
}
Back
|
FazBrowse Home
|
New Git URL