Edmonds karp

Bonjour,
Le remake de la scène d'Ohama beach par 3 graphistes londoniens.

Bonjour,

algorithm EdmondsKarp
input:
C[1..n, 1..n] (Capacity matrix)
E[1..n, 1..?] (Neighbour lists)
s (Source)
t (Sink)
output:
f (Value of maximum flow)
F (A matrix giving a legal flow with the maximum value)
f := 0 (Initial flow is zero)
F := array(1..n, 1..n) (Residual capacity from u to v is C[u,v] - F[u,v])
forever
m, P := BreadthFirstSearch(C, E, s, t)
if m = 0
break
f := f + m
(Backtrack search, and write flow)
v := t
while v ≠ s
u := P[v]
F[u,v] := F[u,v] + m
F[v,u] := F[v,u] - m
v := u
return (f, F)

algorithm BreadthFirstSearch
input:
C, E, s, t
output:
M[t] (Capacity of path found)
P (Parent table)
P := array(1..n)
for u in 1..n
P[u] := -1
P[s] := -2 (make sure source is not rediscovered)
M := array(1..n) (Capacity of found path to node)
M[s] := ∞
Q := queue()
Q.push(s)
while Q.size() > 0
u := Q.pop()
for v in E[u]
(If there is available capacity, and v is not seen before in search)
if C[u,v] - F[u,v] > 0 and P[v] = -1
P[v] := u
M[v] := min(M[u], C[u,v] - F[u,v])
if v ≠ t
Q.push(v)
else
return M[t], P
return 0, P

Cordialement.

l'algorithme de flot max de Edmonds karp en langage c

Voila !
http://academia.edu/3511977/Flot_maximal_par_lalgorithme_dEdmonds-Karp