Vai al contenuto

5.6 L'algoritmo di Edmonds–Karp

Definizione 5.12: algoritmo di Edmonds–Karp

L'algoritmo di Edmonds–Karp è l'algoritmo di Ford–Fulkerson in cui il Passo 1 usa la visita in ampiezza: \(\mathit{LIST}\) è una coda, gli archi residui che escono da ogni nodo sono esaminati per indice crescente della testa, e la visita si ferma appena \(t\) è etichettato. Le capacità sono numeri reali non negativi qualsiasi.

  • Per la Proposizione «BFS trova i percorsi più brevi in numero di archi» del Capitolo 1, il cammino aumentante ha il numero minimo di archi fra i cammini da \(s\) a \(t\) in \(G(\vet{x})\).

  • Per un flusso ammissibile \(\vet{x}\) e un nodo \(i\), \(d_{\vet{x}}(i)\) è il numero minimo di archi di un cammino da \(s\) a \(i\) in \(G(\vet{x})\), e \(d_{\vet{x}}(i)=+\infty\) se \(i\) non è raggiungibile.

  • Un arco del cammino aumentante è critico se la sua capacità residua è uguale a \(\delta\): dopo l'aumento la sua capacità residua è zero, ed esce dalla rete residua.

  • Un aumento lungo \(P\) diminuisce \(r_{ij}\) di \(\delta\) e aumenta \(r_{ji}\) di \(\delta\) su ogni arco \((i,j)\) di \(P\), e non cambia nessun'altra capacità residua. Quindi gli archi che entrano nella rete residua sono inversi di archi di \(P\).

Lemma 5.13: le distanze non diminuiscono

Sia \(\vet{x}'\) ottenuto da \(\vet{x}\) con un aumento lungo un cammino \(P\) da \(s\) a \(t\) di \(G(\vet{x})\) con il numero minimo di archi. Allora \(d_{\vet{x}'}(i) \ge d_{\vet{x}}(i)\) per ogni \(i \in N\).

Dimostrazione

Mostriamo che ogni arco \((a,b)\) di \(G(\vet{x}')\) soddisfa \(d_{\vet{x}}(b) \le d_{\vet{x}}(a)+1\).

  1. Se \((a,b)\) è un arco di \(G(\vet{x})\), un cammino più breve da \(s\) ad \(a\) seguito da \((a,b)\) raggiunge \(b\) con \(d_{\vet{x}}(a)+1\) archi.

  2. Altrimenti \((a,b)\) è l'inverso di un arco \((b,a)\) di \(P\). La parte di \(P\) da \(s\) a ciascuno dei suoi nodi ha il numero minimo di archi: un cammino verso quel nodo con meno archi, seguito dal resto di \(P\), darebbe una passeggiata da \(s\) a \(t\) con meno archi di \(P\), e quindi un cammino più corto al suo interno (Capitolo 1, Lemma «ogni passeggiata contiene un cammino»). Quindi \(d_{\vet{x}}(a)=d_{\vet{x}}(b)+1\), e \(d_{\vet{x}}(b) \le d_{\vet{x}}(a)+1\).

Sia ora \(s=i_0,i_1,\dots,i_q=i\) un cammino di \(G(\vet{x}')\) con \(q=d_{\vet{x}'}(i)\) archi. Lungo i suoi archi \(d_{\vet{x}}\) cresce al più di \(1\) alla volta, quindi \(d_{\vet{x}}(i) \le d_{\vet{x}}(s)+q=d_{\vet{x}'}(i)\). Se \(i\) non è raggiungibile in \(G(\vet{x}')\), allora \(d_{\vet{x}'}(i)=+\infty\). □

Lemma 5.14: archi critici

Nell'algoritmo di Edmonds–Karp, sia l'arco residuo \((i,j)\) critico nell'aumento che parte dal flusso \(\vet{x}\), e di nuovo critico in un aumento successivo, che parte dal flusso \(\vet{y}\). Allora \(d_{\vet{y}}(i) \ge d_{\vet{x}}(i)+2\).

Dimostrazione

Applichiamo il Lemma 5.13 a ogni aumento fra \(\vet{x}\) e \(\vet{y}\).

  1. Con il flusso \(\vet{x}\), l'arco \((i,j)\) sta su un cammino con il numero minimo di archi, quindi \(d_{\vet{x}}(j)=d_{\vet{x}}(i)+1\); dopo l'aumento \(r_{ij}=0\).

  2. Con il flusso \(\vet{y}\) l'arco \((i,j)\) è di nuovo nella rete residua, quindi un aumento intermedio, che parte da un flusso \(\vet{z}\), ha aumentato \(r_{ij}\): il suo cammino usava l'arco inverso \((j,i)\), e \(d_{\vet{z}}(i)=d_{\vet{z}}(j)+1\).

  3. Le distanze non diminuiscono mai, quindi \(d_{\vet{z}}(j) \ge d_{\vet{x}}(j)\) e \(d_{\vet{y}}(i) \ge d_{\vet{z}}(i)\). Ne segue

    \[ d_{\vet{y}}(i) \ge d_{\vet{z}}(i)=d_{\vet{z}}(j)+1 \ge d_{\vet{x}}(j)+1=d_{\vet{x}}(i)+2 . \]

□

Teorema 5.15: tempo di esecuzione di Edmonds–Karp

Per qualsiasi capacità non negativa, l'algoritmo di Edmonds–Karp si ferma dopo al più \(n\,m\) aumenti con un flusso massimo e un taglio minimo, e richiede tempo \(O(n\,m\,(n+m))\), cioè \(O(n\,m^2)\) quando \(m \ge n-1\).

Dimostrazione
  1. Ogni aumento ha almeno un arco critico: un arco di \(P\) la cui capacità residua è uguale a \(\delta\).

  2. Quando \((i,j)\) è critico, \(i\) precede \(t\) su un cammino da \(s\) a \(t\) con al più \(n-1\) archi, quindi \(0 \le d(i) \le n-2\). Per il Lemma 5.14 questa distanza cresce di almeno \(2\) fra due volte in cui l'arco è critico, quindi \((i,j)\) è critico al più \(\lfloor \frac{n-2}{2} \rfloor+1 \le \frac{n}{2}\) volte.

  3. Ogni arco residuo è \((i,j)\) o \((j,i)\) per un arco \((i,j) \in A\): ce ne sono al più \(2m\), e gli aumenti sono al più \(2m \cdot \frac{n}{2}=n\,m\).

  4. Ogni iterazione richiede tempo \(O(n+m)\), come nel Teorema 5.11. All'arresto \(G(\vet{x})\) non ha cammini aumentanti, e il Teorema 5.8 si applica come nella dimostrazione del Teorema 5.9. □

  • Il limite dipende solo da \(n\) e \(m\), non dalle capacità: l'algoritmo di Edmonds–Karp è fortemente polinomiale, e si ferma anche con capacità irrazionali.

5.6.1 Edmonds–Karp sulla rete di riferimento

Esempio 5.8: Edmonds–Karp sulla rete di riferimento

Eseguiamo l'algoritmo sulla rete dell'Esempio 5.1; la colonna «archi» è il numero di archi del cammino aumentante.

iterazione cammino aumentante archi \(r_{ij}\) su \(P\) archi all'indietro \(\delta\) \(v\)
\(1\) \(1,2,4,6\) \(3\) \(5,3,4\) – \(3\) \(3\)
\(2\) \(1,3,5,6\) \(3\) \(4,4,3\) – \(3\) \(6\)
\(3\) \(1,3,5,4,6\) \(4\) \(1,1,2,1\) – \(1\) \(7\)

Le distanze \(d_{\vet{x}}(i)\) nella rete residua prima di ogni visita sono:

iterazione \(d(1)\) \(d(2)\) \(d(3)\) \(d(4)\) \(d(5)\) \(d(6)\)
\(1\) \(0\) \(1\) \(1\) \(2\) \(2\) \(3\)
\(2\) \(0\) \(1\) \(1\) \(3\) \(2\) \(3\)
\(3\) \(0\) \(1\) \(1\) \(3\) \(2\) \(4\)
arresto \(0\) \(1\) \(\infty\) \(\infty\) \(\infty\) \(\infty\)

  • L'iterazione \(1\) è la visita in ampiezza dell'Esempio «BFS dal nodo \(1\)» del Capitolo 1, il cui cammino nell'albero fino al nodo \(6\) è \(1,2,4,6\).

  • Gli archi critici sono \((2,4)\) nell'iterazione \(1\), \((5,6)\) nell'iterazione \(2\), e \((1,3)\), \((3,5)\), \((4,6)\) nell'iterazione \(3\). Quando \((2,4)\) esce dalla rete residua, \(d(4)\) cresce da \(2\) a \(3\); nessuna distanza diminuisce mai.

  • L'algoritmo esegue \(3\) aumenti, contro i \(5\) dell'Esempio 5.6, molto sotto il limite \(n\,m=54\). Termina con lo stesso flusso massimo \(\tilde{\vet{x}}\), l'unico, e con lo stesso taglio \(S=\{1,2\}\).

  • Sulla rete dell'Esempio 5.7 la visita in ampiezza trova \(1,2,4\) e poi \(1,3,4\), ciascuno con \(\delta=M\): due aumenti per ogni \(M\).

L'algoritmo di Edmonds–Karp aumenta il flusso lungo cammini con il minor numero di archi, trovati dalla visita in ampiezza. Le distanze da \(s\) nella rete residua non diminuiscono mai, ogni arco è critico al più \(\frac{n}{2}\) volte, e l'algoritmo esegue al più \(n\,m\) aumenti: tempo \(O(n\,m^2)\), per qualsiasi capacità.


Avanti: 5.7 Applicazioni