Algoritme de Dinic

L'algoritme de Dinic és un algoritme de Temps polinòmic per a la computació d'un Fluix maximal en una ret de fluix, concebuda en 1970 pel científic de la computació Yefim Dinitz, israelita d'orige soviètic. L'algoritme és eixecutat en un temps de $O(V^{2}E)$ i està basat en l'Algoritme d'Edmonds-Karp, el qual a la seua volta s'eixecuta en un temps $O(V{E}^2)$, i utilisa trayectòries d'aument més curtes. L'introducció dels conceptes nivell de grafo i bloqueig de fluix és lo que definix el rendiment de l'algoritme de Dinic.

Definició

Es té el grafo $G=((V,E),c,s,t)$ que serà una ret de fluix en $c(u,v)$ és la capacitat i $f(u,v)$ el fluix de l'arc $(u,v)$.

La capacitat residual és un mapage $c_f:V\times V\to R^{+}$ definit com,

1. Si $(u,v)\in E$,

   $c_f(u,v)=c(u,v)-f(u,v)$

   $c_f(v,u)=f(u,v)$

2. $c_f(u,v)=0$ d'una atra manera.

El grafo residual és el grafo $G_f=((V,E_f),c_f{|}_{E_f},s,t)$, a on

$E_f=\{(u,v)\in V\times V:c_f(u,v)>0\}$.

La trayectòria d'aument és una ruta $s-t$ en el grafo residual $G_f$.

Es definix $\mathrm{dist}(v)$ com la longitut del camí més curt des de $s$ fins a $v$ en $G_f$.Llavors el nivell del grafo de $G_f$ és el grafo $G_L=(V,E_L,c_f{|}_{E_L},s,t)$, a on

$E_L=\{(u,v)\in E_f:\mathrm{dist}(v)=\mathrm{dist}(u)+1\}$.

El bloqueig del fluix és un $s-t$ fluix $f$ de manera tal que el grafo $G^{\prime }=(V,{E_L}^{\prime },s,t)$ en ${E_L}^{\prime }=\{(u,v):f(u,v)<c_f{|}_{E_L}(u,v)\}$ no té cap ruta $s-t$.

Algoritme

Algoritme de Dinic

Entrada: Una ret $G=((V,E),c,s,t)$.

Eixida: Un fluix $s-t$ de valor $f$ maximisat.

1. Es té $f(e)=0$ per a cada $e\in E$.
2. Construir $G_L$ des de $G_f$ de $G$. Si $\mathrm{dist}(t)=\mathrm{\infty }$, detindre i retornar el resultat $f$.
3. Trobar un bloqueig de fluix $f{}^{\prime }$ en $G_L$.
4. Aumentar el fluix $f$ per $f{}^{\prime }$ i tornar al pas 2.

Vore també

• Algoritme de Ford-Fulkerson
• Problema de Fluix Màxim

Referències

• Yefim Dinitz (2006). «Dinitz' Algorithm: The Original Version and Even's Version», Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman (ed.). Theoretical Computer Science: Essays in Memory of Shimon Even, Springer, pp. 218–240. ISBN 978-3540328803. Consultat el 22 d'abril de 2012.
• Tarjan, R. E. (1983). Data structures and network algorithms.
• B. H. Korte, Jens Vygen (2008). «8.4 Blocking Flows and Fujishige's Algorithm», Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics, 21), Springer Berlin Heidelberg, pp. 174–176. ISBN 978-3-540-71844-4.