Merkelapp-metoden for flyt-maksimering

Last ned en Java-version

• Den første beskriver om dette beskriver en flyt inn eller ut fra denne noden.
• Den andre sier hvilke nabonode det er snakk om.
• Den tredje parameteren beskriver mulig flytøkning fram til noden.

Algoritmen:

1. Gi {f(i,j)} en brukbar startflyt (f.eks. {f(i,j)=0})
2. Gi start-noden, S, merkelappen (-,NIL,∞). Sett I={S}.
   Erklær S for ubehandlet. La n=S.
3. Gjør følgende for den merkede og ubehandlede noden n ∈ I: (for alle j)

   a)

   Hvis (n,j) ∈ kant-listen L, j er umerket og f(n,j) < c(n,j), så gi j merkelappen:

   Inn

   n

   min(delta(n), c(n,j)-f(n,j)) = delta(j)

   b)

   I = I U {j}

   c)

   Hvis (j,n) ∈ kant-listen L, j er umerket og f(j,n) > 0, så gi j merkelappen:

   Ut

   n

   min(delta(n), f(n,j)) = delta(j)

   d)

   I = I U {j}

4. n er behandlet (alle j undersøkt).
5. Hvis n ≠ slutt og det eksisterer en ubehandlet n ∈ I: Gå til 3.
6. Hvis n ≠ slutt: {f(i,j)} er optimal, AVSLUTT!
7. Strømforøkende kjede/vei funnet. Utfør for {(i,j)} i kjeden:
   • i → j - type: f(i,j) = f(i,j) + delta(slutt) (forover-kant)
   • i ← j - type: f(i,j) = f(i,j) - delta(slutt) (bakover-kant)
8. Fjern merkelapper. Gå til 2.