Edmonds–Karp algorithm: Difference between revisions

Revision as of 06:25, 5 January 2006

Revision as of 14:21, 7 January 2006

Line 67:

[[Image:ek-flow_0.png]]

In the pairs <math>f/c</math> written on the edges, <math>f</math> is the current flow, and <math>c</math> is the capacity. The residual capacity from <math>u</math> to <math>v</math> is <math>R_{c_f(u,v})=C_{c(u,v})-F_{f(u,v})</math>, the total capacity, minus the flow you have already used. If the net flow from <math>u</math> to <math>v</math> is negative, it ''contributes'' to the residual capacity.

<table width="100%">

Line 77:

<tr>

<td><math>A-,D-,E-,G</math></td>

<td>

<math>\min(R_{c_f(A,D}),R_{c_f(D,E}),R_{c_f(E,G})) = </math></br>

<math>\min(3-0,2-0,1-0) = </math></br>

<math>\min(3,2,1) = 1</math></br>

Line 87:

<tr>

<td><math>A-,D-,F-,G</math></td>

<td>

<math>\min(R_{c_f(A,D}),R_{c_f(D,F}),R_{c_f(F,G})) = </math></br>

<math>\min(3-1,6-0,9-0) = </math></br>

<math>\min(2,6,9) = 2</math></br>

Line 97:

<tr>

<td><math>A-,B-,C-,D-,F-,G</math></td>

<td>

<math>\min(R_{c_f(A,B}),R_{c_f(B,C}),R_{c_f(C,D}),R_{c_f(D,F}),R_{c_f(F,G})) = </math></br>

<math>\min(3-0,4-0,1-0,6-2,9-2) = </math></br>

<math>\min(3,4,1,4,7) = 1</math></br>

Line 107:

<tr>

<td><math>A-,B-,C-,E-,D-,F-,G</math></td>

<td>

<math>\min(R_{c_f(A,B}),R_{c_f(B,C}),R_{c_f(C,E}),R_{c_f(E,D}),R_{c_f(D,F}),R_{c_f(F,G})) = </math></br>

<math>\min(3-1,4-1,2-0,0--1,6-3,9-3) = </math></br>

<math>\min(2,3,2,1,3,6) = 1</math></br>

Line 118:

</table>

Notice how the length of the [[augmenting path]] found by the algorithm never decreases. The paths found are the shortest possible. The flow found is equal to the capacity across the [[max_flow_min_cut_theorem|smallest cut]] in the graph separating the source and the sink. There is only one minimal cut in this graph, partitioning the nodes into the sets <math>\{A,B,C,E\}</math> and <math>\{D,F,G\}</math>, with the capacity <math>C_{c(A,D})+C_{c(C,D})+C_{c(E,G})=3+1+1=5</math>.

==References==