Hvorfor har Edmonds–Karp kjøretid O(VE²)?
Ford-Fulkerson har kjøretid $O(E|f^*|)$, der $|f^*|$ er maks flyt. Dette fordi man potensielt kan øke flyten $E$ ganger. Samme logikk for Edmonds-Karp. Potensielt kan flyten øke $E$ ganger, men hvorfor $O(VE^2)$? Om den bruker BFS, så har vel den kjøretid $O(V+E)$, som totalt gir $O(VE+E^2)$?
Hohoi, ja, godt spørsmål. En litt utfordrende analyse, dette. For det første er jeg ikke helt enig med den første analysen din: Man kan øke flyten (i heltallsinkrementer) \(|f^*|\) ganger, og hver iterasjon har en kjøretid på \(O(E)\). Så med mindre jeg har misforstått hva du mener, så har du byttet om på de to komponentene i Ford-Fulkerson-kjøretidsanalysen. (Og merk at det bare gjelder hvis du har heltallskapasiteter.)
Forskjellen er altså at i stedet for \(|f^*|\) iterasjoner, kan Edmonds-Karp garantere at vi maksimalt bruker \(O(VE)\) iterasjoner. Men hvorfor?
Lemma 24.7: Den korteste veien i residualnettverket fra \(s\) til enhver node \(v\) bortsett fra \(s\) og \(t\) øker eller beholder samme verdi i hver iterasjon.
Bevisskisse: Anta at avstanden til \(v\) synker i en iterasjon. La oss også anta at om dette gjelder flere noder, så har vi valgt den som ligger nærmest \(s\) etter iterasjonen. La oss si den korteste veien til \(v\) i residualnettverket etter iterasjonen ender med kanten \((u,v)\), som betyr at \(u\) ligger ett skritt nærmere \(s\). Siden vi valgte \(v\) som den noden nærmest \(s\) som fikk sin avstand redusert, så kan ikke \(u\) ha fått sin avstand redusert.
Dersom kanten \((u,v)\) eksisterte i residualnettverket før denne iterasjonen, så kunne ikke \(v\) ha hatt en høyere avstand da. Siden vi antok at den fikk sin avstand redusert, kan ikke \((u,v)\) ha eksistert da – den må ha dukket opp i løpet av denne iterasjonen. Den eneste måten det kan ha skjedd på er at flyten må a økt fra \(v\) til \(u\).
Og det kunne jo potensielt ha skjedd om vi brukte en vilkårlig traverseringsalgoritme, som i Ford-Fulkerson generelt. Men: Edmonds-Karp velger alltid den korteste forøkende sti (med BFS), så om den økte flyten fra \(v\) til \(u\) så må den ha fulgt den korteste veien fra \(s\) til \(u\), og den siste kanten i den stien må ha vært \((v,u)\).
Den korteste veien til \(v\) før iterasjonen var én mindre enn den korteste til \(u\). Og samtidig vet vi at den korteste veien til \(u\) etter iterasjonen er én mindre enn den korteste veien til \(v\) etter iterasjonen. Og vi vet at avstanden til \(u\) ikke sank. Den eneste konklusjonen er at den korteste veien til \(v\) før iterasjonen var minst 2 mindre enn den korteste veien til \(v\) etter iterasjonen. Men vi antok jo at den sank! Vi har altså en selvmotsigelse – det er umulig at noen av de korteste avstandene kan synke. (Men det gjelder altså bare fordi vi fant den korteste forøkende stien.)
I Theorem 24.8 bruker de dette resultatet til å vise at en kant \((u,v)\) kan være en flaskehals for en forøkende sti maks \(|V|/2\) ganger. Om den skal ha den til å være en flaskehals igjen etter at den nettopp har vært det må du først ha en forøkende sti som går motsatt vei, for å øke flyten fra \(v\) til \(u\), og så tilbake fra \(u\) til \(v\). Du kan jo se ulikheten på side 729, men – long story short – innen kanten er flaskehals neste gang, vil den korteste veien til \(u\) ha økt med 2. Og det kan jo skje maks \(O(V)\) ganger. I verste tilfelle kan hver kant være flaskehals helt alene i hver iterasjon. Det kan altså skje for hver av de \(E\) kantene, som betyr at vi en flaskehals kan oppstå maksimalt \(O(EV)\) ganger. Det vil si, vi har maksimalt \(O(EV)\) iterasjoner.
Oooog siden hver iterasjon tar \(O(E)\) tid, så blir den totale kjøretiden \(O(VE^2)\). Phew!
Boka sier også at maksimal bipartitt matching er \(O(VE)\). Hvordan er dette raskere, hvis det løses ved å gjøre om til maks flyt og deretter løses? Er det en annen Ford-Fulkerson som brukes, og ikke Edmonds-Karp?
Kjøretiden er både \(O(VE^2)\) og \(O(E|f^*|)\), dvs., begge er gyldige øvre grenser. I dette tilfellet kan ikke flyten bli større enn \(V/2\), så du kan bytte ut \(|f^*|\) med \(V\) i den asymptotiske kjøretiden. Faktisk så betyr det at det ikke er noe poeng i å bruke Edmonds-Karp; du kan like gjerne bare kjøre Ford-Fulkerson med DFS, for eksempel, om du vil det.