Едмондс–Карпов алгоритам — разлика између измена
Садржај обрисан Садржај додат
Нема описа измене |
Нема описа измене |
||
Ред 5:
and [[Clifford Stein]] |title=[[Introduction to Algorithms]] |publisher=MIT Press | year = 2009 |
isbn=978-0-262-03384-8 |edition=third |chapter=26.2 |pages=727–730 }}</ref>
== Pseudokod ==
'''algoritam''' EdmondsKarp
'''ulaz''':
C[1..n, 1..n] ''(matrica kapaciteta)''
E[1..n, 1..?] ''(lista suseda)''
s ''(izvor)''
t ''(ponor)''
'''izlaz''':
f ''(vrednost maksimalnog protoka)''
F ''(matrica koja daje dozvoljen protok sa maksimalnom vrednoscu)''
f := 0 ''(inicijalni protok je nula)''
F := '''niz'''(1..n, 1..n) ''(rezidualni kapacitet od u do v je C[u,v] - F[u,v])''
'''forever'''
m, P := BreadthFirstSearch(C, E, s, t, F)
'''if''' m = 0
'''pauza'''
f := f + m
''(Backtrack pretraga, zapis protoka)''
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)
'''algoritam''' BreadthFirstSearch
'''ulaz''':
C, E, s, t, F
'''izlaz''':
M[t] ''(kapacitet pronadjenog puta)''
P ''(roditeljska tabela)''
P := '''niz'''(1..n)
'''for''' u '''in''' 1..n
P[u] := -1
P[s] := -2 ''(brinemo se da izvor nije ponovo pronadjen)''
M := '''niz'''(1..n) ''(kapacitet pronadjenog puta do cvora)''
M[s] := 8
Q := queue()
Q.offer(s)
'''while''' Q.size() > 0
u := Q.poll()
'''for''' v '''in''' E[u]
''(Ukoliko postoji dostupan kapacitet i v nije vidjeno ranije u pretrazi)''
'''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.offer(v)
'''else'''
'''return''' M[t], P
'''return''' 0, P
== Имплементација у Јави ==
| |||