Edmonds-Karps algoritm

Edmonds-Karps algoritm löser problemet med att hitta det maximala flödet i ett transportnätverk . Algoritmen är ett specialfall av Ford-Fulkerson- metoden och går i tid i grafen . Den publicerades första gången 1970 av den sovjetiske vetenskapsmannen E. A. Dinitz . Senare, 1972, upptäcktes den oberoende av Edmonds och Karp . $O(|V|\cdot |E|^{2})$ $G=(V,E)$

Algoritm

Edmonds-Karp- algoritmen är en variant av Ford-Fulkerson-algoritmen där den kortaste komplementära vägen från till i det återstående nätverket väljs vid varje steg (förutsatt att varje kant har enhetslängd). Den kortaste vägen hittas med bredd-först sökning . $s$ $t$

Beskrivning

Vi återställer alla strömmar. Det återstående nätverket sammanfaller initialt med det ursprungliga nätverket.
I restnätet hittar vi den kortaste vägen från källan till sänkan. Finns det ingen sådan väg så stannar vi.
Vi släpper igenom den hittade banan (det kallas ökande väg eller ökande kedja ) maximalt möjliga flöde:
1. På den hittade vägen i restnätet letar vi efter en kant med minsta kapacitet . $c_{\min }$
2. För varje kant på den hittade banan ökar vi flödet med , och i motsatt riktning minskar vi det med . $c_{\min }$ $c_{\min }$
3. Vi modifierar restnätet. För alla kanter på den hittade banan, såväl som för kanterna mittemot dem, beräknar vi den nya kapaciteten. Om det blir icke-noll, lägger vi till en kant på restnätverket, och om det blir noll, raderar vi det.
Vi återgår till steg 2.

För att hitta den kortaste vägen i en graf använder vi bredd-först-sökning :

Vi skapar en kö av hörn O. Till en början består O av en enda vertex s .
Vi markerar vertexen som besökta, utan förälder, och alla övriga som obesökta.
Så länge kön inte är tom, utför följande steg:
1. Ta bort första hörnet i kön u .
2. För alla bågar ( u , v ) som utgår från vertex u , för vilka vertex v ännu inte har besökts, utför följande steg:
  1. Vi markerar vertex v som besökt, med förälder u .
  2. Lägg till vertex v i slutet av kön.
  3. Om v = t , lämna båda slingorna: vi har hittat den kortaste vägen.
Om kön är tom returnerar vi svaret att det inte finns någon väg alls och stannar.
Om inte går vi från t till s , varje gång vi går till föräldern. Vi går tillbaka vägen i omvänd ordning.

Svårighet

Under arbetets gång kommer Edmonds-Karps algoritm att hitta varje kompletterande väg i tiden . Nedan kommer vi att bevisa att det totala antalet flödesökningar som utförs av denna algoritm är . Således är komplexiteten hos Edmonds-Karp-algoritmen . $O(|E|)$ $O(|V|\cdot |E|)$ $O(|V|\cdot |E|^{2})$

Bevis

Låt oss kalla avståndet från vertex x till vertex y för längden på den kortaste vägen från x till y i det återstående nätverket, mätt med antalet kanter. Om det inte finns någon sådan väg kommer vi att betrakta avståndet som oändligt. Vi kommer att säga att y har närmat sig x (avvikit från x ) om avståndet från x till y har minskat (ökat). Vi kommer att säga att y är närmare x (längre bort från x ) än z om avståndet från x till y är mindre (större) än avståndet från x till z .

Lemma . Under algoritmens gång närmar sig inget hörn någonsin källan. Bevis . Låt detta inte vara fallet, då med en viss ökning av flödet, närmade sig några toppar källan. Låt oss kalla dem fel. Vi väljer en av de felaktiga hörnen, som efter att ha ökat flödet visade sig vara närmast källan (om det finns mer än en av dem, då någon av dem). Beteckna det valda hörnet med v . Betrakta den kortaste vägen från s till v . Beteckna den näst sista spetsen på denna väg med u , så att banan ser ut som . Eftersom u är närmare s än v och v är den olagliga hörn som ligger närmast s , så är u en vanlig hörn. Betecknar avstånden från s till u och v före respektive efter flödesökningen , som , , , , har vi: $s-\ldots-uv$ $d_{u}\$ ${\displaystyle d_{u}^{'))$ $d_{v}\$ $d_{v}^{'}$

d_{v}^{'}<d_{v}

{\displaystyle d_{u}^{'}\geq d_{u))

d_{v}^{'}=d_{u}^{'}+1

var

d_{v}\geq d_{u}+2

Därför, före ökningen av flödet, var bågen ( u , v ) frånvarande från det kvarvarande nätverket. För att den skulle visas måste den utökade banan innehålla en båge ( v , u ). Men i Edmonds-Karp-algoritmen är förstärkningsvägen alltid den kortaste, så

d_{v}=d_{u}-1

vilket strider mot den tidigare ojämlikheten. Så vårt antagande var fel. Lemmat är bevisat.

Låt oss kalla det kritiska för kanterna på förstärkningsbanan, vars restkapacitet är minimal. Låt oss uppskatta hur många gånger någon kant (u, v) kan vara kritisk. Låt det hända vid iteration , och nästa gång vid iteration . Betecknar avståndet från s till y vid iteration t, vi har: $t_{1}$ $t_{2}$ $D_{y}(t)$

D_{v}(t_{1})=D_{u}(t_{1})+1

D_{v}(t_{2})=D_{u}(t_{2})+1

Observera att vid iterationen försvinner den kritiska kanten från det kvarvarande nätverket. För att kanten (u, v) ska dyka upp i den igen vid tiden för iterationen, är det nödvändigt att vid någon mellanliggande iteration en förstärkningsbana som innehåller kanten (v, u) väljs. Följaktligen, $t_{1}$ $t_{2}$ ${\displaystyle t_{3))$

D_{u}(t_{3})=D_{v}(t_{3})+1

Med hjälp av det tidigare beprövade lemmat får vi:

D_{v}(t_{2})=D_{u}(t_{2})+1\geq D_{u}(t_{3})+1=D_{v}(t_{3} )+2\geq D_{v}(t_{1})+2

Eftersom inledningsvis (annars v = s, men kanten som leder till s inte kan visas på den kortaste vägen från s till t), och alltid, när den naturligtvis är mindre än |V| (den kortaste vägen innehåller inte cykler och därför innehåller färre |V|-kanter), kan en kant vara kritisk vid de flesta tillfällen. Eftersom varje förstärkningsväg innehåller minst en kritisk kant och det totala antalet kanter som en dag kan bli kritiska (alla kanter på det ursprungliga nätverket och deras motsatta), så kan vi inte öka sökvägen mer än |E|·|V | en gång. Därför överstiger inte antalet iterationer O(|E|·|V|), vilket skulle bevisas. $D_{v}>0$ ${\displaystyle D_{v))$ ${\frac {(|V|-1)-1}{2}}+1=|V|/2$ $2|E|$

Exempel

Låt ett nätverk ges med source vid vertex och drain vid vertex . I figuren betecknar ett par flödet längs denna kant och dess genomströmning. $A$ $G$ $f/c$

Bredd första sökningen

Låt oss beskriva bredden-första-sökningen i det första steget.

Kön består av en enda vertex A. Hörnen A har besökts. Det finns ingen förälder.
Kön består (från början till slut) av hörn B och D. Hörnena A, B, D besöks. Hörnena B, D har förälder A.
Kön består av hörn D och C. Besöks av A, B, C, D. Hörnen B, D har förälder A, vertex C har förälder B.
Kön består av hörn C, E, F. Besöks av A, B, C, D, E, F. Hörnen B, D har förälder A, vertex C har förälder B, hörn E, F har förälder D.
Vertex C tas bort från kön: dess kanter leder endast till redan besökta hörn.
En kant (E,G) hittas och slingan stannar. Topparna (F,G) är i kön. Alla hörn besökta. Hörnen B, D har förälder A, vertex C har förälder B, hörn E, F har förälder D och vertex G har förälder E.
Vi går efter förälder: . Vi returnerar den passerade banan i omvänd ordning: . $G\to E\to D\to A$ $A\to D\to E\to G$

Observera att hörn som kan nås från A i exakt 1 steg, i exakt 2 steg och i exakt 3 steg lades till sekventiellt i kön. Dessutom är föräldern till varje vertex den hörn som kan nås från A exakt 1 steg snabbare.

Grundläggande algoritm

Bankapacitet	Väg
Bankapacitet
$\min(c_{f}(A,D),c_{f}(D,E),c_{f}(E,G))=$ $\min(3-0.2-0.1-0)=$ $\min(3,2,1)=1$	$A,D,E,G$

$\min(c_{f}(A,D),c_{f}(D,F),c_{f}(F,G))=$ $\min(3-1,6-0,9-0)=$ $\min(2,6,9)=2$	$A,D,F,G$

$\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D),c_{f}(D,F),c_{f} (F,G))=$ $\min(3-0.4-0.1-0.6-2.9-2)=$ $\min(3,4,1,4,7)=1$	$A,B,C,D,F,G$

$\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))=$ $\min(3-1.4-1.2-0.0--1.6-3.9-3)=$ $\min(2,3,2,1,3,6)=1$	$A,B,C,E,D,F,G$

Observera att under exekveringen av algoritmen minskar inte längden på komplementära vägar (indikerade i rött i figurerna). Denna egenskap är uppfylld på grund av att vi letar efter den kortaste kompletterande vägen .

Dinitzs algoritm

En förbättrad version av Edmonds-Karp-algoritmen är Dinitz-algoritmen, som kräver operationer. $O(|V|^{2}|E|)$

Låt oss kalla ett extra konturlöst nätverk av en graf för G med källan s dess subgraf som endast innehåller de kanter (u, v) för vilka det minsta avståndet från s till v är ett större än det minsta avståndet från s till u.

Dinits algoritm:

Vi konstruerar ett minimalt konturlöst nätverk av restgrafen.
Så länge det finns en väg från s till t i nätverket, utför följande steg:
1. Hitta den kortaste vägen från s till t. Om det inte finns, lämna slingan.
2. På den hittade vägen i restnätet letar vi efter en kant med minsta kapacitet . $c_{\min }$
3. För varje kant på den hittade banan ökar vi flödet med , och i motsatt riktning minskar vi det med . $c_{\min }$ $c_{\min }$
4. Vi tar bort alla kanter som har nått mättnad.
5. Vi tar bort alla återvändsgränder (det vill säga hörn, förutom diskbänken, från vilken inga kanter går, och hörn, förutom källan, där inga kanter kommer in), tillsammans med alla kanter som faller in på dem.
6. Upprepa föregående steg så länge det finns något att ta bort.
Om den hittade strömmen inte är noll, lägg till den till den totala strömmen och återgå till steg 1.

Länkar

Litteratur

Thomas Kormen m fl Algoritmer: konstruktion och analys = INTRODUKTION TILL ALGORITHMER. - 2:a uppl. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .

Algoritmer för grafsökning
Oinformerade metoder	Dubbelriktad sökning Strålsökning Lexikografisk bredd första sökning Utöka första sökningen Sök efter kostnadskriterium Djup första sökning Backtracking sökning Sök genom att klättra till toppen Djupbegränsad sökning Djup-första sökning med iterativ fördjupning
Informerade metoder	Alfa beta-klippning Gren och bunden metod Sök efter första bästa matchning A* B* D* Att hitta en övergångspunkt IDA* Rekursiv sökning på den första bästa matchningen SMA*
Genvägar	Vågalgoritm Bellman-Ford algoritm Dijkstras algoritm Johnsons algoritm Levits algoritm Floyd-Warshall algoritm Kantsökning
Minsta spännträd	Boruvkas algoritm Prims algoritm Kruskals algoritm
Övrig	British Museum Algoritm Edmonds algoritm Trädpassering Algoritmen för närmaste granne i problemet med resande säljare