5.6 L'algoritmo Edmonds–Karp¶

Parte 3 · Flussi · Capitolo 5 · Capitolo 5: Flusso massimo · Dispensa, volume 3 (PDF) · Esercizi: Flusso massimo · App: Flusso massimo: Ford–Fulkerson ed Edmonds–Karp

Definizione 5.12: Algoritmo di Edmonds–Karp

L'algoritmo Edmonds–Karp è l'algoritmo Ford–Fulkerson in cui il Passo 1 utilizza l'algoritmo ricerca in ampiezza: \(\mathit{LIST}\) è una coda, gli archi residui che escono da ciascun nodo vengono scansionati aumentando l'indice della testa e la ricerca si interrompe non appena viene etichettato \(t\). Le capacità sono numeri reali non negativi.

Di Capitolo 1, Proposta «BFS trova i percorsi più brevi in numero di archi», il percorso aumentante ha il numero minimo di archi tra i percorsi 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 percorso 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 il aumento la sua capacità residua è zero e lascia la rete residua.
Un aumento lungo \(P\) abbassa \(r_{ij}\) di \(\delta\) e solleva \(r_{ji}\) di \(\delta\) su ogni arco \((i,j)\) di \(P\) e non modifica 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}\) mediante un aumento lungo un percorso \(P\) da \(s\) a \(t\) di \(G(\vet{x})\) con il numero minimo di archi. Quindi \(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\).

Se \((a,b)\) è un arco di \(G(\vet{x})\), un percorso più breve da \(s\) a \(a\) seguito da \((a,b)\) raggiunge \(b\) con Archi \(d_{\vet{x}}(a)+1\).
Altrimenti \((a,b)\) è il rovescio 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 percorso verso quel nodo con meno archi, seguito dal resto di \(P\), darebbe una passeggiata da Da \(s\) a \(t\) con meno archi di \(P\) e un percorso al suo interno (Capitolo 1, Lemma «una 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\).

Ora lasciamo che \(s=i_0,i_1,\dots,i_q=i\) sia un percorso di \(G(\vet{x}')\) con archi \(q=d_{\vet{x}'}(i)\). Lungo i suoi archi \(d_{\vet{x}}\) cresce al massimo di \(1\) alla volta, quindi \(d_{\vet{x}}(i) \le d_{\vet{x}}(s)+q=d_{\vet{x}'}(i)\). Se \(i\) non lo è raggiungibile in \(G(\vet{x}')\), quindi \(d_{\vet{x}'}(i)=+\infty\). □

Lemma 5.14: archi critici

Nell'algoritmo Edmonds–Karp, lasciamo che l'arco residuo \((i,j)\) sia critico nell'aumento al flusso \(\vet{x}\), e nuovamente critico in un successivo aumento al flusso \(\vet{y}\). Quindi \(d_{\vet{y}}(i) \ge d_{\vet{x}}(i)+2\).

Dimostrazione

Applichiamo Lemma 5.13 ad ogni aumento tra \(\vet{x}\) e \(\vet{y}\).

In \(\vet{x}\), l'arco \((i,j)\) si trova su un percorso con il numero minimo di archi, quindi \(d_{\vet{x}}(j)=d_{\vet{x}}(i)+1\); dopo l'ampliamento \(r_{ij}=0\).
In \(\vet{y}\) l'arco \((i,j)\) è tornato nella rete residua, quindi qualche aumento nel mezzo, in un flusso \(\vet{z}\), \(r_{ij}\) rialzato: il suo percorso utilizzava l'arco inverso \((j,i)\) e \(d_{\vet{z}}(i)=d_{\vet{z}}(j)+1\).
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)\). Quindi

\[ 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 Edmonds–Karp si ferma dopo al massimo gli aumenti \(n\,m\) con un massimo flusso e un taglio minimo e viene eseguito nel tempo \(O(n\,m\,(n+m))\), ovvero \(O(n\,m^2)\) quando \(m \ge n-1\).

Dimostrazione

Ogni potenziamento ha almeno un arco critico: un arco di \(P\) la cui capacità residua è pari a \(\delta\).
Quando \((i,j)\) è critico, \(i\) si trova prima di \(t\) su un percorso da \(s\) a \(t\) con al massimo \(n-1\) archi, quindi \(0 \le d(i) \le n-2\). Per Lemma 5.14 questa distanza cresce di almeno \(2\) tra due tempi critici, quindi \((i,j)\) è critico al massimo nei tempi \(\lfloor \frac{n-2}{2} \rfloor+1 \le \frac{n}{2}\).
Ogni arco residuo è \((i,j)\) o \((j,i)\) per un arco \((i,j) \in A\): ce ne sono al massimo \(2m\), e al massimo Miglioramenti \(2m \cdot \frac{n}{2}=n\,m\).
Ogni iterazione richiede tempo \(O(n+m)\), come in Teorema 5.11. Alla fermata \(G(\vet{x})\) non ha cammino aumentante, e Teorema 5.8 si applica come nella dimostrazione di Teorema 5.9. □

Il limite dipende solo da \(n\) e \(m\), non dalle capacità: l'algoritmo Edmonds–Karp è fortemente polinomiale, e si ferma anche alle 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 di Esempio 5.1; la colonna «archi» è il numero di archi del percorso aumentante.

iterazione e percorso incrementale e archi	\(r_{ij}\) su \(P\) e 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 ricerca 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\)

Iterazione \(1\) è la ricerca in ampiezza di Capitolo 1, Esempio «BFS da nodo \(1\)», il cui percorso dell'albero 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 iterazione \(3\). Quando \((2,4)\) lascia la rete residua, \(d(4)\) cresce da \(2\) a \(3\); nessuna distanza diminuisce mai.
L'algoritmo necessita di aumenti \(3\), rispetto a \(5\) di Esempio 5.6, molto al di sotto del limite \(n\,m=54\). Termina con la stessa portata massima \(\tilde{\vet{x}}\), unica, e lo stesso taglio \(S=\{1,2\}\).
Sulla rete di Esempio 5.7 la ricerca in ampiezza trova prima \(1,2,4\) e poi \(1,3,4\), ciascuno con \(\delta=M\): due ampliamenti per ogni \(M\).

L'algoritmo di Edmonds–Karp sceglie, con una ricerca in ampiezza, un cammino aumentante con il minor numero di archi. Le distanze dei nodi da \(s\) nella rete residua non diminuiscono mai. Ogni arco diventa critico al massimo \(\frac{n}{2}\) volte, perciò l'algoritmo esegue al più \(nm\) aumenti e richiede tempo \(O(nm^2)\), indipendentemente dai valori delle capacità.

Avanti: 5.7 Applicazioni