You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: src/graph/edmonds_karp.md
+4-4Lines changed: 4 additions & 4 deletions
Original file line number
Diff line number
Diff line change
@@ -92,20 +92,20 @@ Their minimum is 5, therefore we can increase the flow along this path by 5.
92
92
This gives a flow of 5 for the network.
93
93
<divstyle="text-align: center;">
94
94
<imgsrc="Flow2.png"alt="First path">
95
-

95
+
<imgsrc="Flow3.png"alt="Network after first path">
96
96
</div>
97
97
98
98
Again we look for an augmenting path, this time we find $s - D - A - C - t$ with the residual capacities 4, 3, 3, and 5.
99
99
Therefore we can increase the flow by 3 and we get a flow of 8 for the network.
100
100
<divstyle="text-align: center;">
101
101
<imgsrc="Flow4.png"alt="Second path">
102
-

102
+
<imgsrc="Flow5.png"alt="Network after second path">
103
103
</div>
104
104
105
105
This time we find the path $s - D - C - B - t$ with the residual capacities 1, 2, 3, and 3, and hence, we increase the flow by 1.
106
106
<divstyle="text-align: center;">
107
107
<imgsrc="Flow6.png"alt="Third path">
108
-

108
+
<imgsrc="Flow7.png"alt="Network after third path">
109
109
</div>
110
110
111
111
This time we find the augmenting path $s - A - D - C - t$ with the residual capacities 2, 3, 1, and 2.
@@ -118,7 +118,7 @@ The intuition of it is the following:
118
118
Instead of sending a flow of 3 from $D$ to $A$, we only send 2 and compensate this by sending an additional flow of 1 from $s$ to $A$, which allows us to send an additional flow of 1 along the path $D - C - t$.
119
119
<divstyle="text-align: center;">
120
120
<imgsrc="Flow8.png"alt="Fourth path">
121
-

121
+
<imgsrc="Flow9.png"alt="Network after fourth path">
122
122
</div>
123
123
124
124
Now, it is impossible to find an augmenting path between $s$ and $t$, therefore this flow of $10$ is the maximal possible.
0 commit comments