8000 Update edmonds_karp.md · cp-algorithms/cp-algorithms@659d23b · GitHub
[go: up one dir, main page]

Skip to content

Commit 659d23b

Browse files
authored
Update edmonds_karp.md
Made the explanation of augmenting path a little clearer.
1 parent d0f1a33 commit 659d23b

File tree

1 file changed

+1
-1
lines changed

1 file changed

+1
-1
lines changed

src/graph/edmonds_karp.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -66,7 +66,7 @@ We can create a **residual network** from all these edges, which is just a netwo
6666
The Ford-Fulkerson method works as follows.
6767
First, we set the flow of each edge to zero.
6868
Then we look for an **augmenting path** from $s$ to $t$.
69-
An augmenting path is a simple path in the residual graph, i.e. along the edges whose residual capacity is positive.
69+
An augmenting path is a simple path in the residual graph where residual capacity is positive for all the edges along that path.
7070
If such a path is found, then we can increase the flow along these edges.
7171
We keep on searching for augmenting paths and increasing the flow.
7272
Once an augmenting path doesn't exist anymore, the flow is maximal.

0 commit comments

Comments
 (0)
0