FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
Java/src/main/java/com/thealgorithms/graph/Dinic.java at master · lowtalker/Java · GitHub
lowtalker
Java
Repository navigation
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
Java
/
src
/
main
/
java
/
com
/
thealgorithms
/
graph
/
Dinic.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
119 lines (112 loc) · 4.16 KB
Breadcrumbs
Java
/
src
/
main
/
java
/
com
/
thealgorithms
/
graph
/
Dinic.java
Copy path
File metadata and controls
119 lines (112 loc) · 4.16 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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
package
com
.
thealgorithms
.
graph
;
import
java
.
util
.
ArrayDeque
;
import
java
.
util
.
Arrays
;
import
java
.
util
.
Queue
;
/**
* Dinic's algorithm for computing maximum flow in a directed graph.
*
* <p>Time complexity: O(E * V^2) in the worst case, but typically faster in practice
* and near O(E * sqrt(V)) for unit networks.</p>
*
* <p>The graph is represented using a capacity matrix where capacity[u][v] is the
* capacity of the directed edge u -> v. Capacities must be non-negative.
* The algorithm builds level graphs using BFS and finds blocking flows using DFS
* with current-edge optimization.</p>
*
* <p>This implementation mirrors the API and validation style of
* {@link EdmondsKarp#maxFlow(int[][], int, int)} for consistency.</p>
*
* @see <a href="https://en.wikipedia.org/wiki/Dinic%27s_algorithm">Wikipedia: Dinic's algorithm</a>
*/
public
final
class
Dinic
{
private
Dinic
() {
}
/**
* Computes the maximum flow from source to sink using Dinic's algorithm.
*
* @param capacity square capacity matrix (n x n); entries must be >= 0
* @param source source vertex index in [0, n)
* @param sink sink vertex index in [0, n)
* @return the maximum flow value
* @throws IllegalArgumentException if the input matrix is null/non-square/has negatives or
* indices invalid
*/
public
static
int
maxFlow
(
int
[][]
capacity
,
int
source
,
int
sink
) {
if
(
capacity
==
null
||
capacity
.
length
==
0
) {
throw
new
IllegalArgumentException
(
"Capacity matrix must not be null or empty"
);
}
final
int
n
=
capacity
.
length
;
for
(
int
i
=
0
;
i
<
n
;
i
++) {
if
(
capacity
[
i
] ==
null
||
capacity
[
i
].
length
!=
n
) {
throw
new
IllegalArgumentException
(
"Capacity matrix must be square"
);
}
for
(
int
j
=
0
;
j
<
n
;
j
++) {
if
(
capacity
[
i
][
j
] <
0
) {
throw
new
IllegalArgumentException
(
"Capacities must be non-negative"
);
}
}
}
if
(
source
<
0
||
sink
<
0
||
source
>=
n
||
sink
>=
n
) {
throw
new
IllegalArgumentException
(
"Source and sink must be valid vertex indices"
);
}
if
(
source
==
sink
) {
return
0
;
}
// residual capacities
int
[][]
residual
=
new
int
[
n
][
n
];
for
(
int
i
=
0
;
i
<
n
;
i
++) {
residual
[
i
] =
Arrays
.
copyOf
(
capacity
[
i
],
n
);
}
int
[]
level
=
new
int
[
n
];
int
flow
=
0
;
while
(
bfsBuildLevelGraph
(
residual
,
source
,
sink
,
level
)) {
int
[]
next
=
new
int
[
n
];
// current-edge optimization
int
pushed
;
do
{
pushed
=
dfsBlocking
(
residual
,
level
,
next
,
source
,
sink
,
Integer
.
MAX_VALUE
);
flow
+=
pushed
;
}
while
(
pushed
>
0
);
}
return
flow
;
}
private
static
boolean
bfsBuildLevelGraph
(
int
[][]
residual
,
int
source
,
int
sink
,
int
[]
level
) {
Arrays
.
fill
(
level
, -
1
);
level
[
source
] =
0
;
Queue
<
Integer
>
q
=
new
ArrayDeque
<>();
q
.
add
(
source
);
while
(!
q
.
isEmpty
()) {
int
u
=
q
.
poll
();
for
(
int
v
=
0
;
v
<
residual
.
length
;
v
++) {
if
(
residual
[
u
][
v
] >
0
&&
level
[
v
] == -
1
) {
level
[
v
] =
level
[
u
] +
1
;
if
(
v
==
sink
) {
return
true
;
}
q
.
add
(
v
);
}
}
}
return
level
[
sink
] != -
1
;
}
private
static
int
dfsBlocking
(
int
[][]
residual
,
int
[]
level
,
int
[]
next
,
int
u
,
int
sink
,
int
f
) {
if
(
u
==
sink
) {
return
f
;
}
final
int
n
=
residual
.
length
;
for
(
int
v
=
next
[
u
];
v
<
n
;
v
++,
next
[
u
] =
v
) {
if
(
residual
[
u
][
v
] <=
0
) {
continue
;
}
if
(
level
[
v
] !=
level
[
u
] +
1
) {
continue
;
}
int
pushed
=
dfsBlocking
(
residual
,
level
,
next
,
v
,
sink
,
Math
.
min
(
f
,
residual
[
u
][
v
]));
if
(
pushed
>
0
) {
residual
[
u
][
v
] -=
pushed
;
residual
[
v
][
u
] +=
pushed
;
return
pushed
;
}
}
return
0
;
}
}
Back
|
FazBrowse Home
|
New Git URL