Algorisme Edmonds-Karp

En informàtica i teoria de grafs, l'algorisme d'Edmonds–Karp és una especificació del de Ford–Fulkerson per calcular el flux màxim en una xarxa de flux amb cost ${\mathcal {O}}(|V|\cdot |E|^{2})$ . Aquest és assimpdòticament més lent que l'algorisme reetiqueta endavant que té un cost de ${\mathcal {O}}(|V|^{3})$ , però pot ser més ràpid en grafs dispersos. L'algorisme va ser publicat primer per un científic rus, Yefim (Chaim) Dinic, l'any 1970, i independentment per Jack Edmonds i Richard Karp el 1972 (però descobert abans). L'algorisme de Dinic inclou tècniques addicionals per reduir el temps d'execució a ${\mathcal {O}}(|V|^{2}\cdot |E|)$ .

Algorisme[modifica]

L'algorisme és idèntic al de Ford–Fulkerson a excepció que amb el d'Edmonds-Karp definim l'ordre de cerca per trobar els camins no saturats. El camí trobat ha de ser el més curt entre els que encara tenen capacitat disponible. Aquest pot ser trobat amb la cerca en amplada, comptant que cada aresta val u. El temps d'execució és de ${\mathcal {O}}(|V|\cdot |E|^{2})$ , perquè cada camí no saturat pot ser trobat amb ${\mathcal {O}}(|E|)$ , i com cada cop almenys una de les arestes $E$ es satura, la distància des de l'aresta saturada fins a la font a través del camí no saturat ha de ser més gran que l'últim cop que aquest estava saturat, i la distància és com a molt de $V$ . L'altra propietat de l'algorisme és que la mida del camí no saturat més curt s'incrementa de manera monòtona.

Pseudocodi[modifica]

algorisme EdmondsKarp
entra:
C[1..n, 1..n] (Matriu de capacitat)
E[1..n, 1..?] (Llistes d'adjacents)
s (Font)
t (Pou)
surt:
f (Valor del flux màxim)
F (Una matriu amb els valors dels fluxos resultants)
f := 0 (El flux inicial és zero)
F := array(1..n, 1..n) (La capacitat residual des de u fins v es C[u,v] - F[u,v])
sempre
m, P := CercaEnAmplada(C, E, s, t)
si m = 0
trenca
f := f + m
(cerca backtrack i escriure flux)
v := t
mentre v ≠ s
u := P[v]
F[u,v] := F[u,v] + m
F[v,u] := F[v,u] - m
v := u
retorna (f, F)

algorisme CercaEnAmplada
entra:
C, E, s, t
surt:
M[t] (Capacitat del camí trobada)
P (Taula pare)
P := array(1..n)
per cada u dins 1..n
P[u] := -1
P[s] := -2 (ens assegurem que la font no és redescoberta) 
M := array(1..n) (Capacitat del camí trobat al node)
M[s] := ∞
Q := queue()
Q.push(s)
mentre Q.size() > 0
u := Q.pop()
per cada v dins E[u]
(Si hi ha capacitat disponible, i v no s'havia vist abans en la cerca)
si C[u,v] - F[u,v] > 0 i P[v] = -1
P[v] := u
M[v] := min(M[u], C[u,v] - F[u,v])
si v ≠ t
Q.push(v)
si no
retorna M[t], P
retorna 0, P

Exemple[modifica]

Donada una xarxa de set nodes, font A i pou G, i capacitats com les que es mostren:

En els parells $f/c$ escrits a les arestes, $f$ és el flux actual, i $c$ és la capacitat. La capacitat residual des de $u$ fins $v$ és $c_{f}(u,v)=c(u,v)-f(u,v)$ , la capacitat total menys el flux que ja hi passa. Si el flux des de $u$ fins $v$ és negatiu, aquest col·labora amb la capacitat residual.

Capacitat	Camí
Capacitat	Xarxa resultant
$\min(c_{f}(A,D),c_{f}(D,E),c_{f}(E,G))=$ $\min(3-0,2-0,1-0)=$ $\min(3,2,1)=1$	$A,D,E,G$

$\min(c_{f}(A,D),c_{f}(D,F),c_{f}(F,G))=$ $\min(3-1,6-0,9-0)=$ $\min(2,6,9)=2$	$A,D,F,G$

$\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D),c_{f}(D,F),c_{f}(F,G))=$ $\min(3-0,4-0,1-0,6-2,9-2)=$ $\min(3,4,1,4,7)=1$	$A,B,C,D,F,G$

$\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))=$ $\min(3-1,4-1,2-0,0--1,6-3,9-3)=$ $\min(2,3,2,1,3,6)=1$	$A,B,C,E,D,F,G$

La mida dels camins no saturats que va trobant l'algorisme (en vermell) no decrementa mai. Els camins que es troben són els més curts possible. El flux que es troba és igual a la capacitat del tall mínim del graf, separant la font del pou. Existeix sols un tall mínim en aquest graf, partint els nodes en els conjunts $\{A,B,C,E\}$ i $\{D,F,G\}$ , amb la capacitat

c(A,D)+c(C,D)+c(E,G)=3+1+1=5.\

Implementació en Java[modifica]

import java.io.*;

class FlowGraph
{
	public static final int WHITE = 0, GRAY = 1, BLACK = 2;
	private double[][] flow, capacity, res_capacity;
	private int[] parent, color, queue;
	private double[] min_capacity;
	private int size, source, sink, first, last;
	private double max_flow;

	public FlowGraph(String fileName)
	{
		.. // Read "size" value, "capacity[size][size]" matrix,
		 // as well as "source" and "sink" node indexes (0-based)
		 // from an input text file.
		maxFlow();
	}

	private void maxFlow() // Edmonds-Karp algorithm with O(V³E) complexity
	{
		flow = new double[size][size];
		res_capacity = new double[size][size];
		parent = new int[size];
		min_capacity = new double[size];
		color = new int[size];
		queue = new int[size];

		for (int i = 0; i < size; i++)
			for (int j = 0; j < size; j++)
				res_capacity[i][j] = capacity[i][j];

		while (BFS(source))
		{
			max_flow += min_capacity[sink];
			int v = sink, u;
			while (v != source)
			{
				u = parent[v];
				flow[u][v] += min_capacity[sink];
				flow[v][u] -= min_capacity[sink];
				res_capacity[u][v] -= min_capacity[sink];
				res_capacity[v][u] += min_capacity[sink];
				v = u;
			}
		}
	}

	private boolean BFS(int source) // Breadth First Search in O(V²)
	{
		for (int i = 0; i < size; i++)
		{
			color[i] = WHITE;
			min_capacity[i] = Double.MAX_VALUE;
		}

		first = last = 0;
		queue[last++] = source;
		color[source] = GRAY;

		while (first != last) // While "queue" not empty..
		{
			int v = queue[first++];
			for (int u = 0; u < size; u++)
				if (color[u] == WHITE && res_capacity[v][u] > 0)
				{
					min_capacity[u] = Math.min(min_capacity[v], res_capacity[v][u]);
					parent[u] = v;
					color[u] = GRAY;
					if (u == sink) return true;
					queue[last++] = u;
				}
		}
		return false;
	}

	public void toFile(String fileName)
	{
		.. // Write the results ("flow" matrix and "max_flow" value) to output file.
		 // To be called in the "main()" method.
	}
}

Implementació en C[modifica]

//Edmonds-Karp
//return the largest flow;flow[] will record every edge's flow
//n, the number of nodes in the graph;cap, the capacity 
//O(VE^2) 
#define N 100
#define inf 0x3f3f3f3f
int Edmonds_Karp(int n,int cap[][N],int source,int sink){
	int flow[N][N];
	int pre[N],que[N],d[N],p,q,t,i,j;
	if (source==sink) return inf;
	memset(flow,0,sizeof(flow));
	while (true){
	 memset(pre,-1,sizeof(pre));
		d[source]=inf;p=q=0,que[q++]=source;
		while(p<q&&pre[sink]<0){
			t=que[p++];
			for (i=0;i<n;i++)
				 if (pre[i]<0&&(j=cap[t][i]-flow[t][i]))
					pre[que[q++]=i]=t,d[i]=min(d[t],j);
		}
		if (pre[sink]<0) break;
		for (i=sink;i!=source;i=pre[i])
				flow[pre[i]][i]+=d[sink],flow[i][pre[i]]-=d[sink];
	}
	for (j=i=0;i<n;j+=flow[source][i++]);
 return j;
}

Vegeu també[modifica]