Universitetet i Oslo Institutt for informatikk
Visualisering av grafalgoritmer
Lars Duvaas
Hovedoppgave
Mai 2002
Forord
Denne hovedoppgaven er skrevet som en del av cand.scient graden i An- vendt og Industriell Matematikk ved Institutt for Informatikk, ved Uni- versitetet i Oslo. Det er en fordel om lesere av denne oppgaven er for- trolig med matematisk notasjon og har en grunnleggende matematisk kunnskap fra kombinatorisk optimering. Målet med oppgaven har vært å lage en applikasjon som visualiserer noen utvalgte grafalgoritmer.
Jeg vil takke min veileder, Geir Dahl, for råd og vink gjennom utviklin- gen av applikasjonen og skriving av oppgaven. En stor takk rettes også til Jarle Kasbo og Trude Larssæther for gjennomlesing av oppgaven og min datter Rosita som fikk meg til å innse at det var på tide å avslutte studiene da hun sa:“Pappa, du er ikke voksen du, for du går på skole sånn som meg ennå.”.
Til slutt kan jeg ikke komme utenom hva min lesesal, parken, har betydd for meg. Bedre støtte i gode og vonde dager skal man lete lenge etter.
Parken Forever!
Oslo, mai 2002, Lars Duvaas
Innhold
Forord iii
1 Innledning 1
1.1 Introduksjon . . . 1
1.2 Oppbygging av oppgaven . . . 2
2 Grafteori 3 2.1 Hva er en graf? . . . 3
3 Teoretisk gjennomgang av algoritmene 7 3.1 Minimum spenntre . . . 7
3.1.1 Kruskals algoritme . . . 9
3.1.2 Prims Algoritme . . . 11
3.2 Korteste vei problemet . . . 12
3.2.1 Potensialer . . . 13
3.2.2 Ford-Bellmans Algoritme . . . 14
3.2.3 Dijkstras Algoritme . . . 20
3.3 Maksimum strøm i nettverk . . . 21
3.3.1 Minimum kutt . . . 23
3.3.2 Økende vei algoritmen . . . 24
3.3.3 Maksimum strøm algoritmen . . . 26
3.4 Minimum kostnad strøm i nettverk . . . 26
4 Brukerveiledning 33 4.1 Kort forklaring av applikasjonen . . . 33
4.2 Redigering av noder og kanter . . . 34
4.2.1 Sette kostnader på kanter og noder . . . 36
4.3 GUI funksjonene . . . 37
4.3.1 Menyene . . . 38
4.3.2 Meldingsvinduet . . . 41
4.3.3 Knappenes funksjoner ved kjøring av en algoritme . 42 4.3.4 Valg av rettet eller urettet graf . . . 42
4.4 Bakgrunnsbildet . . . 43
4.5 Å kjøre applikasjonen som en applet . . . 45
4.6 Installasjon av applikasjonen . . . 46
5 Applikasjonens gjennomgang av algoritmene 49 5.1 Forklaring av algoritmene . . . 49
5.2 Kruskals algoritme . . . 50
5.3 Prims algoritme . . . 53
5.4 Ford-Bellmans algoritme . . . 53
5.5 Dijkstras algoritme . . . 57
5.6 Maksimum strøm – Minimum kutt algoritmen . . . 60
5.7 Minimum kostnad strøm . . . 66
INNHOLD vii
6 Til bruk i læring 71
6.1 Læring . . . 71
7 Oppsummering 75 7.1 Konklusjon . . . 76
A Kode 77 A.1 Algoritmer.java . . . 77
A.2 ButtonListener.java . . . 79
A.3 CloseListener.java . . . 80
A.4 Dijkstra.java . . . 81
A.5 DijkstraListener.java . . . 85
A.6 DirectedListener.java . . . 86
A.7 Edge.java . . . 86
A.8 EdgeLine.java . . . 92
A.9 Edit.java . . . 93
A.10EditEdges.java . . . 94
A.11EditVertexes.java . . . 95
A.12ExitAlgListener.java . . . 97
A.13GraphMaker.java . . . 97
A.14FinishListener.java . . . 100
A.15Ford.java . . . 101
A.16FordListener.java . . . 104
A.17General.java . . . 105
A.18Graph.java . . . 106
A.19GraphApplet.java . . . 114
A.20GraphWindow.java . . . 115
A.21KruskalListener.java . . . 137
A.22Kruskals.java . . . 137
A.23Line.java . . . 139
A.24MaxFlow.java . . . 139
A.25MaxFlowListener.java . . . 144
A.26MenuEditEdgesListener.java . . . 144
A.27MyObject.java . . . 145
A.28MenuEditVertexesListener.java . . . 146
A.29MenuFileExitListener.java . . . 146
A.30MenuFileLoadImgListener.java . . . 146
A.31MenuFileNewGraphListener.java . . . 147
A.32MenuFileOpenListener.java . . . 147
A.33MenuFileRemoveImgListener.java . . . 147
A.34MenuFileSaveAsListener.java . . . 148
A.35MenuFileSaveListener.java . . . 148
A.36MenuGraphListener.java . . . 148
A.37MinCostFlow.java . . . 149
A.38MenuViewCapacityListener.java . . . 154
A.39MenuViewCostListener.java . . . 154
INNHOLD ix
A.40MenuViewDemandListener.java . . . 154
A.41MenuViewFlowListener.java . . . 155
A.42MinCostFlowListener.java . . . 155
A.43MyWindowListener.java . . . 155
A.44NextListener.java . . . 156
A.45PrimListener.java . . . 157
A.46Prims.java . . . 157
A.47RunAlgorithm.java . . . 160
A.48RunDijkstra.java . . . 161
A.49RunFord.java . . . 161
A.50RunMaxFlow.java . . . 161
A.51RunPrim.java . . . 162
A.52SaveFile.java . . . 162
A.53StepListener.java . . . 162
A.54TimeDelayListener.java . . . 163
A.55TrashCan.java . . . 163
A.56UpdateListener.java . . . 164
A.57Vertex.java . . . 164
A.58VertexLine.java . . . 168
Bibliografi 171
Kapittel 1
Innledning
1.1 Introduksjon
I denne hovedoppgaven har jeg laget en applikasjon for å visualisere gra- falgoritmer. Grafalgoritmene som presenteres videre går under fagfeltet kombinatorisk optimering. Visualisering av grafalgoritmer viser hvordan hvert steg i de forskjellige algoritmene ser ut og hvordan disse blir ut- ført. Det er derfor lagt vekt på å gjennomgågrafteori og de forskjellige problemene som algoritmene i applikasjonen kan løse. Jeg har fokusert på fire problemer,minimum spenntre,korteste vei,maksimal strøm i nett- verk ogminimum kostnad strøm i nettverk. Alle problemene er typiske nettverksproblemer som lar seg løse effektivt. Felles for alle algoritmene er at de bruker strukturen i grafen til å løse problemene, som kan vises grafisk.
For å løse minimum spenntre problemet har jeg implementert to algo- ritmer,Prims ogKruskals algoritme. Dette er også gjort for korteste vei problemet, der de to algoritmene Dijkstras og Ford-Bellmans algoritme blir brukt. I de siste to problemene brukes det kun en algoritme for hvert problem.
Formålet med hovedoppgaven er å lage en applikasjon studenter kan benytte til å lære seg de ovennevnte algoritmene som er implementert, ved at de kan få en visuell forståelse av hvordan algoritmene løser de ulike problemene. Studentene skal kunne lage og teste algoritmene på grafer de selv lager på en enkel måte. Applikasjonen er derfor helt og
holdent GUI-basert for å gjøre startterskelen så lav som mulig. Når algo- ritmene kjøres vil man i tillegg til visualisering av grafen få meldinger og spørsmål i henhold til det som skjer underveis.
Når det gjelder Ford-Bellmans algoritme har jeg endret på algoritmen som var foreslått i [1], på grunn av at denne ikke var helt korrekt. For- andringen førte til at algoritmen fungerte på en tilfredstillende måte.
1.2 Oppbygging av oppgaven
I kapittel 2 gis en kort innføring i de grunnleggende begrepene innen grafteori. Grafteorien blir grundigere presentert med gjennomgang av de ulike algoritmene i kapittel 3. Jeg velger å gå igjennom grafteorien etterhvert som det blir nødvendig for å forklare eller bevise algoritme- ne. Kapittel 4 er en brukerveiledning til hvordan man skal installere og bruke applikasjonen. I kapittel 5 blir det gjort rede for hvordan algo- ritmene blir gjennomgått av applikasjonen. Man vil her få en grundig gjennomgang av hva de forskjellig fargene som blir brukt når man kjø- rer en algoritme betyr. I kapittel 6 fremmes noen forslag om hvordan applikasjonen kan brukes i læring. Det er ment at applikasjonen skal brukes av studenter i forbindelse med læring av grafteori, og da spesielt hvis det dreier seg om noen av de algoritmene presentert i denne oppga- ven. Til slutt oppsummeres innholdet i oppgaven og de erfaringer som er gjort gjennom arbeidet med denne. Her har jeg også valgt å si noe om hva som kunne ha vært gjort anderledes i forhold til applikasjonen og dens funksjonalitet og innhold.
Kapittel 2
Grafteori
I
I dette kapittelet skal jeg gå igjennom endel grunnleggende grafteori.Det vil her bli nevnt begreper som er sentrale i all grafteori. Ikke alle vil bli forklart like godt, så det anbefales å lese [6],[1] og [2].
2.1 Hva er en graf?
Å gi en enkel forklaring på hva en graf er kan være vanskelig. Kort fortalt kan man si at en graf er en tegning med punkter og rette streker eller piler mellom noen av punktene. Forklaringen er ikke direkte uriktig, men den sier heller ikke noe om hva en graf er, eller hva grafer kan brukes til. Jeg vil derfor gå igjennom en del eksempler så man letter kan se hva grafteori og algoritmene som senere blir forklart kan brukes til. En del grunnleggende begreper og definisjoner blir også tatt med for å gjøre le- singen enklere. Engraf Gbestår av et ordnet parG=(V , E), derV er en endelig mengdenoder ogEen mengdekanter . Har man nodemengden V = {v1, v2, . . . , vn}så må kantmengdenE ⊆ {{vi, vj}|vi, vj ∈ V}. Tal- lenem, nblir brukt for antall kanter og noder som grafen har. Dersom det ikke blir sagt noe annet vilnvære antall noder (n= |V|) ogmvære antall kanter (m= |E|) iG. En kante= {v, w}blir skrevet somevw eller vw. Vi sier at kantene =vw harv ogw som endenoder. Endenodene til e ligger inntil e. Dersom to noder sies å være naboer så finnes det en kant mellom dem. En graf der alle noder har alle andre noder som naboer kalles enkomplett graf. I figur 2.1 ser vi en graf. Vi kaller det en simpel graf siden den ikke har noenløkkerellerparallellekanter. En løk- ke (figur 2.2) er en kant som har begge endene i samme node, det vil si
r s
t
u
v
w
Figur 2.1: En graf
ate=vv, mens parallelle kanter har de samme endenodene. I de fleste eksempler kan man bruke simple grafer, så i teorien og algoritmene som blir gjennomgått her er det antatt at grafen er simpel.
v e=vv
Figur 2.2: En løkke
Grafen i figur 2.1 er en urettet graf. Det vil si at kantene ikke har noen retning. En kantvwkan brukes til å gå fravtilwog omvendt. Vi define- rer enveiP i en graf som en følgev0, e1, v1, . . . , ek, vk hvor hvervier en node ogeier en kant med endenodenevi−1ogvi.P er en vei frav0tilvk, eller en(v0, vk)-vei. Et spenntreHer ensubgraf avG. Medsubgraf men- er vi atH =(V (H), E(H)) består av en delmengde avG =(V (G), E(G)), slik at V (H) ⊆ V (G) og E(H) ⊆ E(G). En kant e ∈ E(H) har de sam- me endene i H som i G. Det betyr at hvis kanten vw ∈ E(H) så må v, w ∈ V (H). Lett forklart så får man en subgraf H ⊆ G ved og fjer- ne noder og kanter i G. Fjerner man en node må man også fjerne alle kanter som er knyttet til denne noden. SubgrafenH erutspennendenår alle nodene i G er med iH, dvs at V (H) = V (G). Er det en vei mellom alle par av noder sier vi at grafen ersammenhengende. Finnes det en vei P = {v0, e1, v1, . . . , vk}, derv0 =vk ogv0, . . . , vk−1 er forskjellige sier vi at vi har ensykel (figur 2.3). Ettreer en sammenhengende subgraf uten sykler. Flere trær blir, logisk nok, kalt en skog. Er treet utspennende så blir det kalt etspenntre(figur 2.4).
Det er mange strukturer og problemer som kan representeres i form
2.1 Hva er en graf? 5
t
r w
s u
v
Figur 2.3: Sykel
s
r w
v u
t
Figur 2.4: Spenntre
av en graf. De vanligste er nettverk, med noder som datamaskiner og kantene er forbindelser mellom dem. Når to maskiner skal kommunisere med hverandre er det hensiktsmessig at de bruker den korteste veien mellom seg til dette. Det finnes enkle algoritmer for å løse korteste vei problemet (se kapittel 3.2). Dersom det skal sendes store datastrømmer og det er gitt en maks kapasitet på forbindelsene (kantene), så eksisterer det algoritmer (maks strøm - min kutt, se kapittel 3.3) for å finne ut hvor mye som maksimalt kan sendes, og i hvilke kanter begrensningen ligger.
Merknad til notasjon i denne oppgaven
I denne oppgaven har jeg brukt notasjon som går utover det som vanlig- vis brukes. I figurer er ofte nodene merket med en stor bokstav. En node som er merket med A vil bli referert til som vA. Det er derfor naturlig
å si at en kant mellomvA ogvB skal refereres til som vAvB ellerevAvB. Jeg har valgt å skrive ateAB er kanten som går mellomvA ogvB.
Kapittel 3
Teoretisk gjennomgang av algoritmene
I
dette kapittelet blir de forskjellige algoritmene gjort rede for. Graf- teorien som ikke ble nevnt i forrige kapittel som trengs for å forklare eller bevise algoritmene, vil bli forklart etterhvert som man trenger den.3.1 Minimum spenntre
Tenk deg et kabelselskap som skal grave ned kabler mellom mange hus.
Det eneste de krever er at det skal være en kontakt mellom alle husene, men den trenger ikke å være direkte. Kabelselskapet vet kostnadene for å grave ned en kabel for de forskjellige par av husene v og w, og de er gitt vedcvw. Problemet for selskapet er å minimere kostnadene for å grave ned kabelen, slik at alle husene er tilkoblet. En slikt problem kan utformes som en graf der nodene er husene, og kantene mellom nodene er de stedene som det er mulig og bygge ut. Hver kantehar en kostnad ce. Dette problemet blir ofte kaltdesign problemet for nettverk. I figur 3.1 er det tegnet opp en graf der nodene er husene og kantene er de potensi- elle kablene man kan legge. Løsningen man søker er det som blir kalt et minimum spenntre, eller mer nøyaktig minimum kostnad spenntre. Det er vanlig å bruke forkortelsenMST. En kant e har kostnaden ce. Vi sier at kostnaden ved et treH =(V (H), T ), derT =E(H), er gitt ved
c(T )=
eX∈T
ce.
Figur 3.1: Design problemet for nettverk
Det er denne kostnaden vi vil ha minst mulig i et MST. Derfor ønsker vi å finne en kantmengde T som utgjør et spenntre, slik at c(T) er minst mulig.
Før vi se nærmere på hvordan man løser et MST problem bør en vite følgende om spenntrær:
Preposisjon 3.1. En kantevw ∈E(G) er en del av en sykel hvis og bare hvis det er en vei frav tilw iG\ {evw}.
Det følger at en sammenhengende graf fortsatt er sammenhengende hvis man fjerner en kant i en sykel.
Preposisjon 3.2. En utspennende sammenhengende subgraf av G er et spenntre hvis og bare hvis det har eksaktn−1kanter.
At det er akkuratn−1 kanter i et spenntre og at det ikke har sykler, er to av de viktigste egenskapene som MST algoritmene setter som krav.
Man bruker preposisjon 3.2 til å finne ut om man har fått et spenntre eller ikke. Algoritmene legger på en og en kant til treet, og når det er lagt tiln−1 kanter har man fått et spenntre og algoritmen kan stoppe. For hver kant som blir lagt til er det viktig at den ikke lager en sykel. Dersom kantenevw lager en sykel, er den overflødig siden det da allerede finnes en vei mellomv ogw (preposisjon 3.1). Dette er det eneste man trenger
3.1 Minimum spenntre 9
å teste. Det som gjenstår da, er å finne ut hvilke kanter man skal prøve å legge til. Vi skal gå igjennom forskjellige strategier for dette, som vil bringe oss frem til de to mest kjente; Kruskals - og Prims algoritme. Vi skal nå se at det er den strategien som virker som den enkleste også er den som fungerer. Jeg har implementert to algoritmer som begge bygger på det samme prinsippet. Dette prinsippet går ut på at det alltid lønner seg å ta detbilligstevalget i hvert steg.
Kruskals algoritme starter med at den bygger ut en skog til den finner et spenntre. Når man starter består skogen av alle nodene uten noen kanter. Algoritmen tar så den kanten med minst kostnad og legger til en skog så lenge den ikke lager en sykel. Den stopper når den har et funnet spenntre, det vil sin−1 kanter. Litt mer presist finner man dette i figur 3.2.
Kruskals Algoritme
Begynn med en utspennende skogH =(V , F )avG, med F= ∅
For hvert steg legger men til F den kanten e ∉ F med minst kostnad slik atH fortsatt er en skog.
Stopp nårH er blitt et spenntre.
Figur 3.2: Kruskals Algoritme
Prims algoritme er ikke så veldig forskjellig fra Kruskals algoritme, det er bare en liten forskjell i hvordan den bygger ut spenntreet. Den begynner med et tre istedenfor en skog som Kruskals, og legger til den kanten som har minst kostnad av kantene ut fra treet så lenge det ikke dannes en sykel. Treet den starter med er bare en enkel node. I figur 3.3 er algoritmen forklart bedre.
Teorem 1. For enhver sammenhengende grafG med vilkårlig kantkost- naderc, vil Kruskals - og Prims algoritme finne et minimum spenntre.
Beviset for teorem 1 kan leses i [1].
3.1.1 Kruskals algoritme
Jeg vil videre gå igjennom hvordan jeg har implementert Kruskals al- goritme. I figur 3.4 ser du en grovskisse på hvordan jeg har implemen-
Prims Algoritme
Ha et tre H = (V (H), T ) med V (H) = {r} til å starte med for enr ∈V, ogT = ∅.
For hvert steg legger man en kant e ∉ T med minst kostnad tilT slik atH fortsatt er et tre.
Stopp nårH er et spenntre.
Figur 3.3: Prims Algoritme
tert algoritmen. Selve implementasjonen til algoritmen kan leses i til- legg A.22. Denne algoritmen er ikke implementert for at den skal være rask. Man kan heller si at den er ganske treg. Når man skal finne om en kante skal legges til skogen F sjekkers det om den lager en sykel i F. Dette kan implementeres på forskjellige måter. Jeg har valgt en me- tode som ikke er særlig effektiv og ikke bruker strukturen til F særlig godt. Metoden som skal finne en sykel prøver å gå til den finner samme kanten som den startet med. Siden det kan væren−1 kanter i grafen når dette sjekkes, og det skal gjøresmganger, vil vi dette gi en kjøretid på O(mn). Jeg har gjort det på denne måten, fordi metoden også blir brukt i andre algoritmer som ikke har samme struktur somF. Hvis man istedenfor å lete etter sykler sjekker om en kante har endene i to for- skjellige deler avH, så blir algoritmen enda raskere. Dette kan gjøres på logntid, så etter å ha sortertE kan kantene velges ut ved O(mlog n) tid. Det andre som tar tid i en slik algoritme er å sortere alle kantene iE
Kruskals Algoritme
SorterE som{e1, e2, . . . , em}, derce1 ≤ce2≤ · · · ≤cem; SettH=(V , F )medF = ∅;
Setti=0 ogj=0;
Så lengei < n−1 ogj < m j=j+1;
Hvisej ikke lager en sykel iH=(V , F ) Leggej tilF;
i=i+1;
Figur 3.4: Kruskals Algoritme
etter kostnaden c. Jeg har valgt å brukequicksort til å sortere kantene.
Quicksort kjører på en gjennomsnittstid påO(N logN)ogO(N2)i vers-
3.1 Minimum spenntre 11
te tilfelle. MedN menes her antall elementer i listen som skal sorteres.
Kruskals algoritme skal da først sortere mkanter. Etter det er det bare å gå igjennom alle kantene en gang, noe som kan gjøres vedO(mlogn) tid. Vi får da en algoritme som kjører påO(mlogm)tid. Sidenm=n2 (i en komplett graf) får vi at algoritmen kan kjøre påO(mlogn).
3.1.2 Prims Algoritme
Det kan gjøres noen forenklinger på Prims algoritme ved å innføre et nytt begrep, nemlig kuttet til en mengde. For en graf G = (V , E) og L ⊆ V, sier vi at kuttet til L, δ(L) er gitt ved {e ∈ E : e har en ende i Log en ende i V \L}. I figur 3.5 er L= {vD, vC}og kuttet til Lblir da δ(L)= {eCE, eCF, eCH, eCB, eDA, eDE}. Disse kantene er merket med rødt.
Man kan dermed se at algoritmen kan bli som i figur 3.6. Dersom grafen
Figur 3.5: Et kuttδ(L), medL= {vC, vD}
er sammenhengende vil Prims algoritme finne MST. Den enkleste måten å sjekke om algoritmen har funnet MST, er å sjekke om den harn−1 kan- ter når den terminerer. Dersom antall kanter iT er mindre ennn−1 har vi funnet et tre med minimum kostnad. Kruskals algoritme er kanskje en bedre algoritme hvis grafen ikke er sammenhengende. Den finner ikke bare et minimum-kostnad tre, men alle minimum-kostnad trær i grafen.
Algoritmen er implementert med en vektor som holder på alle kantene iδ(V (H)). For hvert steg må vi gå igjennom denne vektoren for å finne den kantene∈δ(V (H))med minimum-kostnad. Siden det kan værem kanter og dette må gjentasn−1 ganger får vi en algoritme som kjører påO(mn)tid. Måten algoritmen er implementert på gjør nok at den får enda litt dårligere kjøretid, siden den for hvert steg viser hvilke kanter
Prims Algoritme
Begynn med et tre H = (V (H), T ), der V (H) = {r} og T = ∅;
Så lengeδ(V (H))6= ∅
Legg tilT en minimum-kostnad kant fraδ(V (H)).
Figur 3.6: Prims Algoritme
som ikke lenger kan være med i spenntreet. Flere forbedringer kan det leses om i [1].
3.2 Korteste vei problemet
Den ideelle taxisjåfør vil fra et bestemt sted alltid vite korteste vei fra dette stedet til alle andre steder. Byen kan tegnes opp som en rettet graf G = (V , E) der V = {v1, v2, . . . , vn} og en node v er et sted man kan kjøre til. Kantene E = {e1, e2, . . . , en} er rettede, siden en vei kan være enveiskjørt. En kante=vwer dermed ikke samme kanten some=wv.
Det er naturlig å tenke at man bare trenger korteste vei fra en sted til et annet. Men som vi snart skal se, så gir korteste vei algoritmene ut korteste vei fra en node til alle andre noder. Jeg velger å kalle dette KVT (Korteste Vei Tre). Når man har funnet korteste vei fra en node til alle andre noder, vil man ha et tre med startnoden som rot. I figur 3.7 ser du et KVT med vA som startnode. Man skulle tro at det er langt mer
Figur 3.7: De blå kantene og nodene utgjør et KVT medvA som rot.
komplisert å finne korteste vei fra en node til alle andre noder, enn bare
3.2 Korteste vei problemet 13
fra en node til en annen. Som vi videre skal få se så tar dette like lang tid.
Når man snakker om en rettet graf brukes nesten akkurat de samme definisjonene som i en urettet graf. En kante ∈E har en halet(e) ∈ V og ethodeh(e)∈V. Kantene=vw harv=t(e)ogw =h(e). Dersom kanten ei i veien P : v0, e1, v1, . . . , ek, vk har t(ei) = vi−1 og h(ei) = vi sier vi at det er en forover kant i P. Er den ikke forover, er den en bakoverkant. En vei hvor alle kantene er forover kalles en rettet vei. Det samme gjelder for en sykel. Er alle kantene forover er det en rettet sykel.
Parallelle kanter har samme hode og samme hale.
Kostnadene for en kantei er gitt vedcei. En rettet vei frav0tilvk, der P = {v0, e1, v1, e2, v2, . . . , ek, vk} og ei= {vi−1, vi}, får da kostnadenc(P )=Pk
i=1cei. Vi antar også atGer simpel. Parallelle kanter kan gjøres om til en enkel kant ved å velge den kanten e med minst kostnadce og en løkkeemed kostnadce ≥0 vil aldri være med i en korteste vei. Er kostnaden ce < 0 vil det ikke finnes noen løsning på korteste vei problemet da det vil lønne seg og gå rundt løkka uendelig mange ganger. Dette er det samme som skjer nårG har negative sykler, som vi skal se nærmere på senere.
3.2.1 Potensialer
Potensialer er den grunnleggende ideen som brukes i alle metoder for å løse korteste vei problemet. Anta at det finnes en rettet vei frar til v.
La kostnaden på denne væreyv for allev∈V. Hvis vi kan finne en kant vw∈Eslik atyv+cvw < yw ser vi at det finnes en vei tilw ved å legge vw til den rettede veien til v. Vi ser da at vi har funnet en rettet vei til w med mindre kostnad,yv +cvw. Det viser seg at hvis yv, der v ∈V, er en minimum kostnad for en rettet vei frar til v, da tilfredstillery
yv+cvw ≥yw, for allevw∈E. (3.1) Dersomy tilfredstiller (3.1) ogyr = 0 sier vi aty tilfredstiller et tillatt potensiale.
Preposisjon 3.3. Lay være et tillatt potensial og laP være en rettet vei frar tilv. Da erc(P )≥yv.
Bevis. Anta atP erv0, e1, v1, e2, . . . , ek, vk, hvorv0=r ogvk =v. Da er c(P )=
Xk
i=1
cei≥ Xk
i=1
(yvi−yvi−1)=yvk−yv0 =yv.
Legg merke til at man ikke trenger å huske på en rettet vei for hver node v∈V. Faktisk trenger man bare huske på en kant for hver nodev≠r. Tenk deg at du har funnet korteste veiP frar tilv. Hvis det er en node w som ligger påP, dvs
P = {r , e1, v2, e2, . . . , vk, ek, w, ewvk+1, vk+1, ek+1, . . . , v},
kan man splitte oppP iP1 ogP2, derP1er korteste vei frar tilw ogP2
er korteste vei fraw tilv. HvisP1ikke hadde vært korteste vei kunne vi byttet den ut og fått mindre kostnad påP. Deler man opp P enda mer ser vi at det bare er den kanten med hode i v man trenger og huske.
Siden det vil væren−1 slike kanter og den korresponderende subgrafen vil inneholde en vei fra r til alle andre noder, vet vi at disse kantene vil utgjøre et spenntre avG. Vi har nå gått ut fra at det finnes en rettet vei frar til alle andre noder v ∈ V. De nodene som det ikke finnes en rettet vei til kan vi se bort fra, fordi disse ikke har noen innvirkning på potensialene.
3.2.2 Ford-Bellmans Algoritme
Ford-Bellmans algoritme er en utvidelse av Fords algoritme. Fords algo- ritme skal finne korteste vei fra en noder til alle andre noderv som det går en rettet vei til.
Man har en graf G = (V , E), der V er nodene og E er en mengde med rettede kanter. Fords Algoritme og Ford-Bellmans Algoritme bruker po- tensialer for å finne en optimal løsning. Begge algoritmene leter til de har funnet et tillatt potensiale. Hvis man finner en kantvw som ikke til- fredstiller (3.1), bytter vi utyw medyv+cvw. For hver nodev∈V\ {r} trenger vi bare å holde rede på den kanten som har hode iv. Disse blir lagret i en “forgjenger”p(v) for hver v ∈ V. Hvis kanten vw ikke til- fredstiller (3.1) så setter man yw = yv +cvw og setter p(w) = v. Vi initiere y og p ved å sette yv = ∞ og p(v) = −1 for v ∈ V \r, og yr = 0 og p(r ) = 0. Når p(v) = −1 betyr dette at det ikke er funn- et en minimum-kostnad vei til v. Antar at 0,−1 ∉ V. En kant vw i en
3.2 Korteste vei problemet 15
Fords Algoritme
Steg 1. Settyv = ∞ogp(v)= −1 forv∈V\r ogyr =0 ogp(r )=0.
Steg 2. Så lenge y ikke tilfredstiller et tillatt potensiale, finn en kant vw som ikke tilfredstiller (3.1) og sett yw =yv+cvw ogp(w)=v.
Figur 3.8: Fords Algoritme
minimum-kostnad vei vil tilfredsstilleyv+cvw =yw. Vi ser at Fords Al- goritme (figur 3.8) vil terminere når den har funnet et tillatt potensiale.
Men det er ikke sikkert at dette eksisterer.
Figur 3.9: Negativ sykel
Figur 3.9 viser at en vei frar tilahar kostnad 1 hvis man går langs kan- tener a. Men går man en “runde”, det vil si følger veien
P = {a, eab, b, ebd, d, edf, f , ef a, a}, vil man ende opp ia. Nå vil kostna- den frar til a være 0. For hver “runde” man går vil kostnaden minke med 1. Kostnaden vil gå mot −∞ ettersom antall “runder” går mot∞. Fords Algoritme vil ikke terminere dersom det finnes en negativ sykel i grafen. En graf der alle kostnaderce≥0, e∈Evil aldri ha en negativ sy- kel og Fords algoritme vil da alltid terminere. Etter at den har terminert vil det eksistere en korteste vei fra r til v dersom yv 6= ∞. Den vil ha
kostnadenyv. Hvisp(v)6= −1 vilyv være den minste kostnaden på en vei frar til v. Det er bare negative sykler som gjør at Fords algoritme ikke vil terminere. For å løse dette skal vi se nærmere på hvordan Fords algoritme går igjennom kantene.
I Fords algoritme er det ikke gitt noen strategi på hvordan man skal gå igjennom kantene som skal sjekkes. Vi kan kalle rekkefølgen som Fords algoritme går igjennom kantene forS. Forskjellige valg av S vil i mange tilfeller føre til dårlig gjennomførelse av algoritmen. Det er derfor vanskelig å si noe om effektiviteten til algoritmen. LaP være den rettede veienv0, e1, v2, . . . , ek, vk frar =v0 tilv =vk. Hvis Fords algoritme ser på kantenee1, e2, . . . , ek, i den rekkefølgen, vil vi ha atyv ≤c(P ). Vi sier atP er inneholdtiS dersom kantene tilP forekommer som en delfølge av S. Det betyr at de ligger i rekkefølge, men ikke nødvendigvis etter hverandre.
Preposisjon 3.4. Hvis Fords algoritme bruker følgenS, da vil vi forv∈V og for hver veiP frar tilvinneholdt i Sha atyv ≤c(P ).
Dersom man kan finne en S slik at alle noder v har en rettet korteste vei inneholdt iS, vil algoritmen terminere. Dette bringer oss inn på Ford - Bellmans algoritme. Legg først merke til atalleenkle rettede veier iG er inneholdt i S = S1, S2, . . . , Sn−1, der Si for alle i er en ordnet følge avE. Når det brukes en slik ordnet følge i Fords algoritme snakkes det om hvor mange gangerE gjennomgåes . Siden hver kant blir behandlet med konstant tid vil algoritmen brukeO(mn) tid. Algoritmen blir kalt Ford - Bellmans algoritme siden Bellman var den første som beviste en polynomisk grense for en slik algoritme. Dersom det ikke er noen rettet negativ kostnad sykel, vil det være nok medn−1 gjennomløpinger avE for å finne et tillatt potensial. Det vil igjen si at det eksisterer en rettet negativ kostnad sykel hvisy ikke tilfredstiller et tillatt potensiale etter n−1 gjennomløpninger avE.
Teorem 2. Ford - Bellmans algoritme finner den rettede minimum-kostnad vei frar tilvfor allev∈V (hvisi < nved terminering), eller den påviser at det fins en rettet negativ-kostnad sykel (hvisi= nved terminering). I begge tilfeller bruker denO(mn)tid.
Siden denne algoritmen (figur 3.10) går igjennom alle kantenenganger hvis det er en rettet negativ-kostnad sykel sier det seg selv at det kan ta lang tid å vise hvert steg i denne algoritmen grafisk. Det betyr at det i praksis blir mnsteg. I en graf med 8 noder og 2 kanter per node, dvs 16 kanter, vil da algoritmen bruke 128 steg, noe som er ganske mye
3.2 Korteste vei problemet 17
Ford-Bellmans Algoritme
Sett yv = ∞ ogp(v) = −1 forv ∈ V \r ogyr = 0 og p(r )=0;
Setti=0;
Så lengei < nogyikke tilfredstiller et tillatt potensiale Setti=i+1;
Fore∈E
Hviseikke tilfredstiller et tillatt potensiale Rett påe;
Figur 3.10: Ford-Bellman Algoritme
for en liten graf som denne. Jeg har derfor lagt inn noen forfininger av algoritmen. Algoritmen vil fortsatt kjøre på tidO(mn), men i praksis vil den bruke mye kortere tid. Metoden er basert på å skanne noder.
Mengden Lv er alle kanter som har hale i v. Med å skanne v menes følgende :
Forvw∈Lv
Hvisvw ikke tilfredstiller et tillatt potensiale Rett på vw;
En naturlig forfining av Ford-Bellmans algoritme er da og bytte ut de siste tre linjene med
Forv∈V Skannv;
Man bør da legge merke til at man ikke trenger åskannev hvisyv ikke er forandret siden sist manskannetv. Man lager to køerQ1 ogQ2. Hvis man retter på en kantvw, det vil si atyw blir forandret, legger man til w i Q2. Begge køene blir laget som FIFO-køer, det vil si at den noden som blir lagt til køen først, er den som først går ut. Forskjellen er at man i hver iterasjon av algoritmen bare skanner de som ble lagt til iQ2 i forrige iterasjon. Dette går i de fleste tilfeller mye fortere enn å skanne alle nodene hver gang. Algoritmen blir da som i figur 3.11. Det er denne versjonen av algoritmen som er blitt implementert i programmet.
Algoritmen i fig 3.11 er en rettelse på forslaget til en forfining som er beskrevet i [1]. Der brukes bareenkøQ, imotsetning til at jeg har brukt
Ford-Bellmans Algoritme
Sett yv = ∞ ogp(v) = −1 for v ∈ V \r ogyr = 0 og p(r )=0;
Setti=0 ogQ1= {r}; Så lengei < nogQ16= ∅
Setti=i+1;
Forv∈Q1 SlettvfraQ1;
Forvw ∈Lv
Hvis vw ikke tilfredsstiller et tillatt poten- sial
Rett påvw;
Leggw tilQ2 hvisw ∉Q1, Q2;
SettQ1=Q2 ogQ2= {};
Figur 3.11: Ford-Bellmans Algoritme med skanning av noder Ford-Bellmans Algoritme, med en kø
Sett yv = ∞ , p(v) = −1 for v ∈ V \r , yr = 0 og p(r )=0;
SettQ= {r}; Forv∈Q
SlettvfraQ;
Forvw∈Lv
Hvisvw ikke tilfredsstiller et tillatt potensial Rett påvw;
Leggw tilQhvisw∉Q;
Figur 3.12: Ford-Bellmans Algoritme med en kø og skanning av noder
to køer Q1 og Q2. Jeg skal videre vise at det går raskere å bruke en kø på grafer som ikke har negative sykler, men at algoritmen ikke vil terminere dersom det eksisterer en negativ sykel i grafen. Algoritmen som er forklart i [1] legger en nodevtilQdersomyvhar blitt forandret, og velger neste node til å bli skannet fra Q (og sletter den fraQ).Q er initielt {r} og algoritmen stopper når Q blir tom. Men som vi skal se av følgende eksempel vil Q aldri bli tom dersom grafen inneholder en negativ sykel. Det er nok å se på hvordanQ(køen) vil bli med grafen fra
3.2 Korteste vei problemet 19
figur 3.9.
Steg 1 Steg 2 Steg 3 Steg 4 Steg 5 Steg 6 Node som blir
skannet og fjern- et fraQ
r a b d f a
Noder som legg-
es tilQ a b d d a b
Q(etter at noder er fjernet og lagt til)
a b d d a b
Tabell 3.1:Q’s utvikling på grafen i figur 3.9
I tabell 3.1 ser vi hvordan køenQvil bli seende ut etter 6 steg. Vi ser at steg 2 og steg 6 er helt like. Siden det ikke er andre stoppkriterier enn at Q skal være tom, noe den aldri blir, vil ikke algoritmen terminere. I [1] refereres det til [4]. Selv om det i [4] tillates negative kostnaderc på kantene, så sies det også at detikkekan være negative sykler i grafen, og at det er negative sykler som gjør at ikke algoritmen terminerer. Å holde orden på to køer krever litt mer testing og operasjoner i hver iterasjon, så algoritmen i [4] vil være raskere enn min implementasjon for grafer som ikke inneholder negative sykler.
Ettersom vi vet fra teorem 2 at Ford-Bellmans algoritme finner den ret- tede veien med minimum kostnad frar til vfor allev∈V, eller påviser at det finnes en rettet sykel med negativ kostnad, trenger jeg bare å vise at algoritmen i figur 3.11 går igjennom alle kantene som trengs i hvert steg. Eller sagt på en annen måte; det må vises at de kantene som ikke blir gjennomgått ikke trenger å bli sjekket. Ford-Bellmans algoritme, slik den er beskrevet i figur 3.10, går igjennom alle kantene i hvert steg. Hvis man heller bruker skanning av noder, så skal alle nodene skannes hver gang. Men siden man bare trenger å skanne en node v dersom yv har blitt senket siden sist gang det ble skannet noder er dette litt tungvint.
Derfor legges alle noder som skal bli skannet neste gang i køen Q2. Så hver gang man skulle gått igjennom alle nodene iV trenger man bare å gå igjennom nodene som ble lagt tilQ2. Ettersom man bare trenger å gå igjennom n−1 ganger for å finne et tillatt potensiale, skal det ikke bli gjort noen forandringer påy når vi går igjennom for n’te gang. Dermed skal det ikke legges noen noder tilQ2. Hvis det er noder som fortsatt må skannes når i = n må det derfor finnes en negativ sykel. Av dette kan det formuleres følgende teorem :
Teorem 3. Ford-Bellmans algoritme med skanning av noder, som i fi- gur 3.11, finner den rettede veien med minimum kostnad frar til v for allev∈V (hvisi < nved terminering), eller den påviser at det finnes en rettet sykel med negativ kostnad (hvisi=nved terminering).
3.2.3 Dijkstras Algoritme
Et spesialtilfelle av korteste vei problemet er når alle kostnadenece ≥0.
Mange problemer som har med korteste vei å gjøre kan beskrives med kostnader som er større eller lik 0. Det viser seg at det er nok å skanne alle nodene en gang, men at det er rekkefølgen man skanner nodene i som har noe å si her. Dersom v1, v2, . . . , vi har blitt skannet, skal den neste nodenvi+1 som blir valgt være den nodenv, som ikke er skannet og har den minste yv. Alle nodene legges fra starten av i S = V, og etterhvert som en node blir skannet blir den fjernet fraS. Man skal legge merke til følgende når noden som blir skannet er valgt på denne måten.
Preposisjon 3.5. For hverw ∈V, layw0 være verdien til yw nårw skal bli skannet. Hvisuer skannet førv, da eryu0 ≤yv0.
Bevis. Anta aty0v < y0uog lavvære den noden som tidligst ble skan- net som dette er sant. Nåruble valgt til å bli skannet varyu0 =yu≤yv, såyv ble senket til en verdi mindre ennyu0 etter atuble valgt til å bli skannet, men førv ble valgt. Såyv ble senket når en nodew ble skan- net, og den ble satt tilyw0 +cwv. Når v ble valgt varyw0 ≥yu0 og siden cwv ≥0 for man aty0v≥y0u, en motsigelse.
Videre kan man se at en kantvw tilfredstiller et tillatt potensiale hvisw har blitt skannet allerede. Nårv blir skannet ogw har blitt skannet før, vet vi fra preposisjon 3.5 atyv ≥yw. Dermed trenges det bare å sjekke om yv +cvw ≤ yw når w ∈ S. Algoritmen blir da som i figur 3.13.
Mengden Lv, der v ∈ V, er alle kanter med hale i v. Det viser seg at algoritmen bare går igjennom kantene en gang, og man skulle tro at det ikke ble mer ennm steg. Men for hver gang det skal skannes en node må man finne den nodenv ∈ S som haryv minimum. Det viser seg at dette ikke er så enkelt som først antatt. Når|S| =kmå man gjørek−1 sammenlikninger ogn−1+n−2+· · ·+1=O(n2)sammenlikninger i alt.
Så kjøretiden blirO(n2). Dette er ganske mye bedre enn Ford-Bellmans algoritme som har en kjøretid påO(mn). Merk atm som regel er mye større ennn. I en komplett graf erm=n2.
3.3 Maksimum strøm i nettverk 21
Dijkstras Algoritme
Sett yv = ∞ ogp(v) = −1 forv ∈ V \r ogyr = 0 og p(r )=0;
SettS=V; Så lengeS6= ∅
Velgv∈S medyv minimum;
SlettvfraS;
Forvw∈Lv ogw ∈S
Hvisvw ikke tilfredstiller et tillatt potensial Rett påyw;
Figur 3.13: Dijkstras Algoritme
3.3 Maksimum strøm i nettverk
Anta at det skal kjøre så mange lastebiler som mulig fra et stedr i et ga- tenettverk til et annet steds. For hver gateeer det en øvre grenseue på hvor mange lastebiler som kan brukee. Dette problemet kan formuleres i en rettet grafG. Målet er da å prøve å finne en familie(P1, . . . , Pk), derPi er en rettet(r , s)-vei. Disse veiene trenger ikke være forskjellige. To eller flere lastebiler kan kjøre samme vei hvis det ikke bryter med kapasiteten på noen av kantene. Ønsket er derfor å maksimerek. Begrensingen, eller kapasitetenue vil i dette eksemplet være heltallig. Algoritmen tilpasset kapasiteter u som er heltallige. En årsak til dette er at i praktiske pro- blemer finnes ofte tall som kan gjøres om til heltallige ved å justere de litt. Vi kan anta at G er simpel, siden strømmen i en løkke er 0 og to parallelle kantere1 oge2 kan skrives som en kantemedue =ue1+ue2. Som regel kalles noden r for kilde ogs for sluk. Det “renner” en strøm fra kilden til sluket. Det er klart at det som blir sendt fra kilden skal komme til sluket. Det kreves derfor at strømmen x inn til nodene skal være lik strømmen ut av nodene for allev∈V\ {r , s}. Med strømmenx menes at hver kante sender strømmenxe. Man sier derfor at vi har en (r , s)-strøm med verdik. Vi definerer funksjonen
fx(v)= X
wv∈E
xwv− X
vw∈E
xvw, (3.2)
som strømmen inn tilv. Man sier derfor atfx(s)er verdien tilx. Det er også klart atfx(r )= −fx(s), siden alt som sendes ut avr skal inn tils.
Å maksimere strømmenxer derfor det samme som å maksimerefx(s).
Faktisk så kan en heltallig strømx deles opp i en familie av veier.
Preposisjon 3.6. Det eksisterer en familie (P1, . . . , Pk) av rettede (r , s)- veier slik at|{i : Pi bruker e}| ≤ue for allee ∈ E hvis og bare hvis det eksisterer en heltallig tillatt(r , s)-strøm med verdik.
Bevis. Bevis kan leses i [1]
Det vil være mest naturlig å tenke at en(r , s)-strøm x er optimal hvis man ikke kan finne en vei P der xe < ue for alle e ∈ P. Dette er der- imot ikke tilstrekkelig. I figur 3.14 ser du en tillatt strøm med verdi 2.
Der ervA = r og vF = s. Her kan man ikke finne en rettet veiP fra r til s med xe < ue for alle e ∈ P, men strømmen er allikevel ikke op- timal. Istedenfor å lete etter en rettet vei hvor strømmen er mindre en
Figur 3.14: Lovlig strøm med verdi 2.
kapasiteten ser vi heller etter en veiP hvorx kan økes. Vi leter etter en (r , s)-veiP derxe< ue hviseer forover iP ogxe>0 hviseer bakover iP. En slik veiP blir kalt enx-økendeeller en strøm-økende vei. Hvis vi kan finne en slik veiP kan strømmen x økes med på kantene som er forover iP og minkes medpå kantene som er bakover iP.er her gitt ved
= min(1, 2), der
1 = min(ue−xe :eforover iP )og 2 = min(xe:ebakover iP ).
(3.3) Det viser seg faktisk at strømmen x er optimal dersom det ikke eksis- terer noenx-økende (r , s)-vei. Jeg skal nå gå nærmere inn på hvor be- grensningen i en(r , s)-strøm ligger.
3.3 Maksimum strøm i nettverk 23
3.3.1 Minimum kutt
Begrensningen tilx ligger iu. På en kant emåxe ≤ue. På noen kanter e ∈ E så må xe = ue, hvis ikke så kunne man øke strømmen til dette skjedde. Vi kaller en mengde δ(R) = {vw : vw ∈ E, v ∈ R, w ∉ R} for en R ⊆ V for et kutt. Legg merke til at δ og kutt blir definert på en litt forskjellig måte for rettede grafer enn det blir for en en urettet graf som på side 11. I figur 3.15 ser vi en strøm med fx(vI) = 7. vI ersluket, mens vB erkilden. Begrensingen tilx ligger i de røde kantene som utgjør minimum kutt.Rer her lik{vB, vA, vC, vF, vD, vE}ogδ(R)= {eF H, eDH, eEG}. Legg merke til ateGD∉δ(R). MengdenRer gitt vedV\R derR⊆V. Det betyr atδ(R)er alle kanter som går inn tilR. I figur 3.15 erδ(R)= {eGD}.
Figur 3.15: Minimum kutt i rettet graf. Her erR= {vB, vA, vC, vF, vD, vE} ogδ(R)er da de røde kantene
Et(r , s)-kutt er et kutt hvorr ∈Rogs∉R. Det er klart at strømmen fra r til s ikke kan overstige kapasiteten til et(r , s)-kutt. Utfra dette kan vi formulere følgende preposisjon:
Preposisjon 3.7. For enhver lovlig (r , s)-strøm x og ethvert (r , s)-kutt δ(R)har vi at
fx(s)≤ X
e∈δ(R)
ue.
Dersom man kan finne et (r , s)-kutt med samme verdi som en (r , s)- strøm, vet vi at vi har maksimum strøm og minmum kutt. Det viser seg at for enhver lovlig maksimum (r , s)-strøm eksisterer det et tilsvarende (r , s)-kutt med samme verdi. Dette fører oss fram til maksimum strøm minimum kutt teoremet.
Teorem 4. (Maksimum strøm Minimum kutt teoremet) Hvis det er en maksimum(r , s)-strøm, da er
maks{fx(s):xen lovlig(r , s)−strøm}
=
min{u(δ(R)):δ(R)et(r , s)−kutt}.
Bevis. Bevis kan leses i [1] og [2].
Preposisjon 3.8. Hvisxer en lovlig(r , s)-strøm ogδ(R)er et(r , s)-kutt, da erxmaksimum ogδ(R)er minimum hvis og bare hvis
xe =ue, for allee∈δ(R)ogxe=0, for allee∈δ(R). (3.4)
Bevis. Bevis kan leses i [1]. side 41-42
3.3.2 Økende vei algoritmen
Å finnex-økende veier i G vil vise seg å være nok til å finne en algorit- me som løser maksimum strøm minimum kutt problemet effektivt. Man begynner med en tillatt strømx (x =0 er en tillatt strøm) og leter etter x-økende veier. Finner man en x-økende vei P øker man x med , gitt ved (3.3). Vi kallerfor x-breddentil P. Dersom x-bredden til en vei er
∞ finnes det ingen maksimal strøm, eller vi sier at den er ubegrenset.
Strømmen x er maksimal hvis det ikke finnes noen x-økende veiP fra r til s og mengdenR = {v : det eksisterer en x-økende vei fra r til v} lager et minimum kutt.
Vi trenger her en metode på hvordan vi skal finne en x-økende veier.
Definerer enrettet hjelpegraf G(x), som avhenger avG,u, og nåværende strømx, som følgende; LaV (G(x))= V og puttvw ∈E(G(x))hvis og bare hvis vw ∈ E og xvw < uvw eller wv ∈ E og xwv > 0. Begge disse tilfellene kan oppstå, og det blir derfor nødvendig å legge inn to parallelle kantervw til E(G(x)). Siden det kan være parallelle kanter i hjelpegrafen G(x) er det vanskelig å tegne den. Jeg vil heller vise den x-økende veien i G. I figur 3.16 ser vi en hjelpegraf G(x), laget utfra strømmen i figur 3.14. Dersom det finnes en rettet (r , s)-vei P i G(x) finnes det også enx-økende veiP0iG. Vi kan i figur 3.16 se at det finnes en rettet(r , s)-veiP. VeienP går igjennom nodene i denne rekkefølgen:
{A, C, D, B, E, F}. Vi kan øke strømmenx langs P med 1. Som man kan se på figur 3.16, så er det noen kanter som står med negativ strøm og at
3.3 Maksimum strøm i nettverk 25
Figur 3.16: Hjelpegraf
kapasiteten er 0 (kanten DB harxDB = −1 og uDB = 0). Dette er fordi den kantenDB ∈G(x) tilsvarer er en kantBD∈Gsom harxBD>0. Så at strømmenxDB ∈G(x)er negativ, betyr at strømmenxBD påBD ∈G kan minkes.
Effektiviteten til algoritmen vil nå være avhengig av hvor mange gang- er vi må lete etter x-økende veier. Uheldige valg avx-økende veier kan gjøre at algoritmen bruker veldig lang tid og at den ikke terminerer hvis strømmen kan være ubegrenset. Det viser seg derimot at det ikke skal store beregninger til for å unngå dette. Hvis man alltid velger den kor- teste x-økende veien P, det vil si den veien som bruker færrest kanter, vil man unngå disse problemene. Så ved å bruke korteste x-økende vei algoritmen, kan det bevises at maksimum strøm problemet kan løses på O(nm2) tid. Det vil lønne seg å bruke et bredde først søk når man skal finne en korteste x-økende vei. Siden det i dette programmet ikke er hastighet som er viktigst, har jeg valgt Dijkstras algoritme isteden.
Grunnen til dette er for å gjøre implementeringen av algoritmen enklere.
I hjelpegrafenG(x)setter jeg alle kostnadene til 1, og bruker Dijkstras algoritme til å finne den korteste veien frar tils.
Det viser seg at problemet også lar seg løse dersom kapasitetene er ra- sjonelle tall og det finnes en maksimal strøm. Er det derimot irrasjonelle kapasiteter, kan det være at algoritmen ikke terminerer, eller som det ble vist i [3] kan den konvergere mot en strøm forskjellig fra maksimum.
3.3.3 Maksimum strøm algoritmen
Algoritmen slik jeg har implementert den blir som i figur 3.17. Jeg lager først en hjelpegraf ,G(x), og bruker så Dijkstras algoritme til å finne korteste vei iG(x), før jeg øker strømmen langs denne veien iG.
Maksimum strøm algoritmen Settxe=0 for allee∈E;
Så lenge det eksisterer en x-økende veiP frar tils Øk strømmen langs kantene påP med min(1, 2), der1=min(ue−xe :eforover iP )
og2=min(xe :ebakover iP );
Figur 3.17: Maksimum strøm algoritmen
Hvordan finne minimum kutt?
Hvordan skal man finne minimum kuttet? Ettersom jeg bare er interes- sert i dette etter at jeg har funnet en maksimal(r , s)-strøm er ikke dette så vanskelig.
Jeg velger å bygge ut R til alle kanter i e ∈ δ(R) har xe = ue og alle kantere∈δ(R)harxe=0. Det er det samme som og setteRlik{v ∈V: det eksisterer en x-økende vei fra r til v}. Vi har dermed en mengde δ(R) som utgjør et (r , s)-kutt. Fra preposisjon 3.8 vet man at dette er et minimum kutt. For å finne kantene i δ(R)kan man gå igjennom alle kantenevw∈Emedv∈R. De kantenevw∈Esom da harxvw =uvw ogw ∈Rutgjørδ(R). Algoritmen for å finne minimum kutt blir da som i figur 3.18. Istedenfor å gå igjennom alle kantenevw ∈ E medv ∈ R går jeg bare gjennom de som harv ∈R ogxvw =uvw. Disse er lagret i Cog jeg trenger da bare å sjekke atw∉R.
3.4 Minimum kostnad strøm i nettverk
Minimum kostnad strøm i nettverk er en liten utvidelse av maksimum strøm problemet. Alle nodene har et behovbv. En nodev ∈V med be- hovbv <0 kan ses på som en node som produserer strøm. Tilsvarende
3.4 Minimum kostnad strøm i nettverk 27
Minimum kutt algoritme Leggr tilRogQ;
Så lengeQ≠∅ Ta utv fraQ;
For allevw,w∈E Hvisuvw =xvw
Leggvw tilC;
Ellers
Hvisw ∉R
Leggw tilRogQ;
For allewv,w ∈E
Hvisxwv >0 ogw ∉R Leggw tilR ogQ;
For allevw∈C Hvisw∈R
Fjernvw fraC;
Figur 3.18: Minimum kutt algoritme
kan de nodenev∈V medbv >0 ses på som noder som trenger strøm.
For at regnestykket skal gå opp kreves det at summen av behovene skal være null,P
v∈Vbv =0. Jeg vil, som i de andre algoritmene jeg har gått igjennom, bare ta for meg heltallsproblemet.
Anta at man har kraftstasjonerk∈K, derK⊂V ogbk <0 som produs- erer strøm og enheterf ∈F, derF ⊂V ogbf >0 som bruker strøm. For hver kraftlinjee har man en kostnad ce som sier noe om hvor mye det koster å sende strøm over denne kraftlinjen. Man har også en kapasitet ue på hver kraftlinje. Man ønsker å minimere kostnadenP
e∈Ecexe, der xe er strømmen som blir sendt gjennom kraftlinje e. Dette problemet blir et minimum kostnad strøm i nettverk problem. Det kan formuleres på følgende måte:
Minimer P
e∈Ecexe (3.5)
Slik at
fx(v)=bv, for allev∈V 0≤xe≤ue for allee∈E.
I tillegg kan man merke seg at summen av behovene må bli 0,P
v∈Vbv =
0, for at det skal kunne eksistere en lovlig strømx.
Vi skal nå se på hvordan man kan finne en lovlig strøm x. Dette kan gjøres ved å bruke maksimum strøm algoritmen og ved at man endrer litt på grafenG. Forandringen går ut på å legge til to noder r og s. Til hver nodev∈V som harbv <0 legger man til en kantr vmed kapasitet ur v = −bv og til hver node w ∈ V som har bw ≥ 0 legger man til en kantwsmed kapasitetuws=bv. I figur 3.21 har vi lagt til to slike noder.
Noden r er i den figuren blitt kalt G, mens s er blitt kalt H. I den nye grafen man har fått ved å legge til to noder og tilhørende kanter bruker, man en maksimum strøm algoritme med r som kilde og s som sluk.
Dersom maksimum strøm algoritmen finner en strøm med verdi fx(s)= X
vs∈E
uvs (3.6)
har man funnet en tillatt strøm for minimum kostnad strøm problemet.
Dette illustreres i figur 3.22 og figur 3.23.
Videre for å finne en optimal strøm skal vi se på en algoritme ikke ulik den vi gikk igjennom for maksimum strøm. Istedenfor å snakke om en x-økende vei prøver man å finne en x-økende sykel . Målet er å finne en sykelS som minker den totale kostnadenP
e∈Ecexe ved at man øker strømmen iS. For at dette skal skje måS ha negativc-kostnad. Til dette defineres en hjelpevariabelce0.
ce0 =
( ce hviseer forover iS
−ce hviseer bakover iS (3.7) Shar negativ c-kostnad hvis
X
e∈S
ce0 <0. (3.8)
Hvis det finnes en slik sykelS kan strømmen økes medlangsS. Her er gitt ved
= min(1, 2), der
1 = min(ue−xe:e forover iS)og 2 = min(xe :ebakover iS).
(3.9) Det vi si at man øker strømmenxetil vi når kapasitetenuei kantene som er forover iSeller til strømmenxeer 0 i kantene som er bakover iS. Men hvordan skal man finne slike syklerS? Svaret er å bruke nesten samme teknikk som vi brukte i maksimum strøm problemet. Vi lager en hjel- pegrafG(x) (figur 3.24) på samme måte som det ble gjort i maksimum strøm algoritmen. LaV (G(x))=V og puttvw∈E(G(x))med kostnad cvw0 =cvw hvis og bare hvisvw ∈ E og xvw < uvw. Legg ogsåvw til E(G(x)) med kostnad cvw0 = −cwv for hver wv ∈ E med xwv > 0. I
