Proyecto 5

Descripción

En la Ciencia de la computación y teoría de los grafos, el Algoritmo de Edmonds-Karp es una implementación del Algoritmo de Ford-Fulkerson para la resolución del problema de flujo máximo en una red de flujo. La característica que lo distingue es que el camino de aumento más corto es usado en cada interacción, lo que garantiza que lo calculo va a terminar. En la mayoría de las implementaciones, el camino de aumento más corto es encontrado usando una búsqueda en anchura, la cual rueda un tiempo de Lo(VE2). Es decir asintóticamente más lento que algoritmo remarcagem-para-frente, el cual rueda en Lo(V3), pero es frecuentemente más rápido para utilización en grafos esparsos. El algoritmo fue publicado por primera vez por el científico ruso Dinic, en 1970, y después, de forma independiente, por Edmonds y Karp que lo publicaron en 1972. El algoritmo de Dinic incluye técnicas adicionales para reducir el tiempo para la orden de Lo(V2Y)

Problema que resuelve

Este algoritmo es idéntico al Algoritmo de Ford-Fulkerson, excepto que la orden de búsqueda cuando encuentra que el camino de aumento de flujo definido. El camino encontrado debe ser el camino más corto con capacidad disponible. Esto lo podemos encontrar por una primera búsqueda de amplitud dejando que los bordes sean la unidad de longitud. El tiempo de duración de O(|V|*|E|^2) se encuentra mostrando que cada trayectoria de aumento se puede encontrar en O(|E|)tiempo, y que a su vez al menos uno de los bordes de E se satura, la distancia desde un borde saturado a la fuente de la trayectoria de aumento debe ser más larga que la última vez que estaba saturado y la distancia es en la mayoría de V de largo.

Ejemplo

Dato una red de siete nudos, y capacidad como mostrado abajo:

En el pares f / c escritos en los arcos, f es el flujo actual, y c es la capacidad. La capacidad residual de u para v es cf(u,v) = c(u,v) − f(u,v), la capacidad total, menos la que ya está siendo usada. Si el flujo de la red de u para v es negativo, esto contribuye para capacidad residual.



Pseudocodigo

//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<0){ t="que[p++];" i="0;i
if (pre[i]<0&&(j=cap[t][i]-flow[t][i])) i="sink;i!=" i="pre[i])" j="i=">
return j;
}





Bibliografia
ww.cse.ohio-state.edu/~tamaldey/course/794/ek-algo.pdf
www.cs.umass.edu/~barring/cs611/lecture/11.pdf

Algoritmo de edmonds karp

View more presentations from ras2043.