Edmonds–Karp algorithm: Difference between revisions

Revision as of 22:55, 12 April 2024

Revision as of 09:54, 31 May 2024

Line 61:

{| class="wikitable"

|-

! Capacity

! Path

! Capacity

! Resulting network

|-

| align="center" | <math>A,D,E,G</math>

| <math>\begin{align}

& \min(c_f(A,D),c_f(D,E),c_f(E,G)) \\

Line 70 ⟶ 71:

= & \min(3,2,1) = 1

\end{align}</math>

|align="center"| <math>A,D,E,G</math>

| [[Image:Edmonds-Karp flow example 1.svg|300px]]</td>

|-

| align="center" | <math>A,D,F,G</math>

| <math>\begin{align}

& \min(c_f(A,D),c_f(D,F),c_f(F,G)) \\

Line 78 ⟶ 79:

= & \min(2,6,9) = 2

\end{align}</math>

|align="center"| <math>A,D,F,G</math>

| [[Image:Edmonds-Karp flow example 2.svg|300px]]</td>

|-

| align="center" | <math>A,B,C,D,F,G</math>

| <math>\begin{align}

& \min(c_f(A,B),c_f(B,C),c_f(C,D),c_f(D,F),c_f(F,G)) \\

Line 86 ⟶ 87:

= & \min(3,4,1,4,7) = 1

\end{align}</math>

|align="center"| <math>A,B,C,D,F,G</math>

| [[Image:Edmonds-Karp flow example 3.svg|300px]]</td>

|-

| align="center" | <math>A,B,C,E,D,F,G</math>

| <math>\begin{align}

& \min(c_f(A,B),c_f(B,C),c_f(C,E),c_f(E,D),c_f(D,F),c_f(F,G)) \\

Line 94 ⟶ 95:

= & \min(2,3,2,1,3,6) = 1

\end{align}</math>

|align="center"| <math>A,B,C,E,D,F,G</math>

| [[Image:Edmonds-Karp flow example 4.svg|300px]]</td>

|}