Mostra la font per a Algorisme Edmonds-Karp

En [[informàtica]] i [[teoria de grafs]], '''l'algorisme d'Edmonds–Karp''' és una especificació del de [[Algorisme de Ford–Fulkerson|Ford–Fulkerson]] per calcular el [[flux màxim]] en una [[xarxa de flux]] amb cost <math>\mathcal{O}(|V| \cdot |E|^2)</math>. Aquest és assimpdòticament més lent que [[l'algorisme reetiqueta endavant]] que té un cost de <math>\mathcal{O}(|V|^3)</math>, però pot ser més ràpid en [[Graf dispers|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 <math>\mathcal{O}(|V|^2 \cdot |E|)</math>.

== Algorisme ==
L'algorisme és idèntic al de [[Algorisme de Ford–Fulkerson|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 <math>\mathcal{O}(|V| \cdot |E|^2)</math>, perquè cada camí no saturat pot ser trobat amb <math>\mathcal{O}(|E|)</math>, i com cada cop almenys una de les arestes <math>E</math> 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 <math>V</math>. L'altra propietat de l'algorisme és que la mida del camí no saturat més curt s'incrementa de manera monòtona.

== Pseudocodi ==
 '''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 ==
Donada una xarxa de set nodes, font A i pou G, i capacitats com les que es mostren:

[[Fitxer:Edmonds-Karp flow example 0.svg|300px|Exemple]]

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

{| class=wikitable
|-
!rowspan=2| Capacitat
! Camí
|-
! Xarxa resultant
|-
|rowspan=2| <math>\min(c_f(A,D),c_f(D,E),c_f(E,G)) = </math><br/>
<math>\min(3-0,2-0,1-0) = </math><br/>
<math>\min(3,2,1) = 1</math><br/>
|align=center| <math>A,D,E,G</math>
|-
| [[Fitxer:Edmonds-Karp flow example 1.svg|300px|Exemple 1]]</td>
|-
|rowspan=2| <math>\min(c_f(A,D),c_f(D,F),c_f(F,G)) = </math><br/>
<math>\min(3-1,6-0,9-0) = </math><br/>
<math>\min(2,6,9) = 2</math><br/>
|align=center| <math>A,D,F,G</math>
|-
| [[Fitxer:Edmonds-Karp flow example 2.svg|300px|Exemple 2]]</td>
|-
|rowspan=2| <math>\min(c_f(A,B),c_f(B,C),c_f(C,D),c_f(D,F),c_f(F,G)) = </math><br/>
<math>\min(3-0,4-0,1-0,6-2,9-2) = </math><br/>
<math>\min(3,4,1,4,7) = 1</math><br/>
|align=center| <math>A,B,C,D,F,G</math>
|-
| [[Fitxer:Edmonds-Karp flow example 3.svg|300px|Exemple 3]]</td>
|-
|rowspan=2| <math>\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)) = </math><br/>
<math>\min(3-1,4-1,2-0,0--1,6-3,9-3) = </math><br/>
<math>\min(2,3,2,1,3,6) = 1</math><br/>
|align=center| <math>A,B,C,E,D,F,G</math>
|-
| [[Fitxer:Edmonds-Karp flow example 4.svg|300px|Exemple 4]]</td>
|}

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 [[teorema de flux màxim tall mínim|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 <math>\{A,B,C,E\}</math> i <math>\{D,F,G\}</math>, amb la capacitat
:<math>c(A,D)+c(C,D)+c(E,G)=3+1+1=5.\ </math>

== Implementació en Java ==
<syntaxhighlight lang="java">
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.
	}
}</syntaxhighlight>

== Implementació en C ==
<syntaxhighlight lang="c">

//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;
}
</syntaxhighlight>

== Vegeu també ==
* [[Problema del flux màxim]]
* [[Teorema de flux màxim tall mínim]]
* [[Tall (graf)]]

[[Categoria:Algorismes de grafs]]