6.2 Korteste vei — BFS, Dijkstra, DAG og reversert graf

Korteste-vei-verktøykassen — BFS (uvektet), Dijkstra (ikke-negative vekter), DAG via topsort, Bellman-Ford (fakta) — og det avgjørende reversert-Dijkstra-trikset.

60 min

7 oppgaver

Korteste veiBFSDijkstraDAGreversert graf

Din fremgang i kapitlet

0 / 7 oppgaver

Kapitlets plass i kurset

Bygger på

6.1Topologisk sortering og DAG-egenskaper

Brukes videre i

6.3Minimale spenntrær — Prim, Kruskal, Borůvka

Korteste vei er i 7 av 7 sett (100 %) — men nesten aldri som «håndkjør
Dijkstra og oppgi tabellen». Faget tester det på to helt andre måter:

- Sjanger F — matriseavkryssing, altså at du krysser av hvilken algoritme som
passer hvilken graftype. Dette er det tryggeste Del 1-poenget i hele Del 6, og
det er fire faste rader du skal kunne uten å tenke deg om.
- Sjanger H — grafalgoritme i pseudokode, altså at du selv skriver algoritmen
og oppgir kjøretiden. Her er det ett bestemt grep som skiller B fra A:
å snu grafen i stedet for å kjøre Dijkstra én gang per utgangspunkt.

Prioritet: høyeste for matrisen (du bør kunne de fire radene i søvne), og
kunne for reversert Dijkstra (nivå 2 — den er A/B-skillet, ikke
bestått-grensen).

Det er verdt å si tydelig hva som ikke kommer: du blir sjelden bedt om å føre
en Dijkstra-tabell steg for steg i et ferdig oppsett. Du blir bedt om å velge
riktig algoritme og skrive den ned. Håndkjøringen i dette kapitlet er derfor
et middel til å forstå algoritmen, ikke et mål i seg selv — den ligger i
kap. 6.5 i drillform.

Slik er kapitlet lagt opp (60 min): fire løkker med tidsanslag, og
pausepunkter etter løkke 2 og løkke 3. Dette er det lengste kapitlet i Del 6.

Sist du var her — forkunnskaper i kortform

Tre resultater fra tidligere kapitler brukes hele veien her. De står ferdig
oppfrisket, så du slipper å bla:

1. Bredde-først-søk (BFS) besøker nodene lagvis. Fra startnoden tas først alle
naboer, så alle naboers naboer, og så videre. Kjøretiden er
$O(|V| + |E|)$ : hver node tas ut av køen én gang, hver kant behandles én gang.
Detaljene står i kap. 5.2.

2. Min-heapen tar ut det minste elementet i $O(\log n)$ . Den er et array med
indeks fra 0; forelder til $i$ er $\lfloor (i-1)/2 \rfloor$ , og barna er $2i+1$ og
$2i+2$ . RemoveMin koster $O(\log n)$ , og det samme gjør Insert og
DecreaseKey. Se kap. 4.4. Dette er prioritetskøen Dijkstra
bruker, og hele Dijkstras kjøretid kommer derfra.

3. Topologisk sortering ordner en DAG slik at alle kanter peker framover, i
$O(|V| + |E|)$ med Kahns algoritme. Se kap. 6.1. Det er
grunnen til at en vektet DAG kan løses raskere enn en generell graf.

Trenger du å friske opp hva en naboliste er, står det i
kap. 5.1.

Notasjons- og pseudokodeliste

Løkke 1 — når alle skritt koster like mye (ca. 10 min)

Et gangveinett mellom åtte bygg. Alle strekkene tar omtrent like lang tid å gå, så
det eneste som teller, er hvor mange strekk du må innom. Hvor mange strekk er
det fra bygg $A$ til bygg $H$ ?

Når alle kanter koster det samme, er korteste vei det samme som færrest kanter,
og da trenger du ingen prioritetskø. Bredde-først-søket tar nodene i den
rekkefølgen de ligger fra startnoden: først alle som er ett skritt unna, så alle
som er to skritt unna. Første gang du når en node, er det via den korteste veien —
det ligger i selve lagvis-rekkefølgen.

📜BFS gir korteste vei i uvektet graf

I en graf uten vekter (eller der alle vekter er like), gir bredde-først-søk fra
$s$ korteste avstand fra $s$ til alle andre noder, målt i antall kanter.

Hvorfor: BFS tar nodene ut av køen i ikke-synkende avstandsrekkefølge. Alle
noder med avstand 1 tas ut før noen med avstand 2, og så videre. Første gang en
node oppdages, skjer det derfor fra en node på laget rett foran — og det er en
korteste vei.

Kjøretid: $O(|V| + |E|)$ . Hver node legges i køen og tas ut nøyaktig én gang,
og hver kant ses på nøyaktig én gang (to ganger i en urettet graf, én gang fra hver
ende — det endrer ikke orden).

Merk hva som gjør dette galt for vektede grafer: BFS teller kanter. En vei med
to dyre kanter er kortere i antall kanter enn en vei med tre billige, men kan
være mye lengre i kostnad. Å bruke BFS på en vektet graf er en av de faste
fellene på matrisen.

✏️Eksempel 1: BFS i gangveinettet

Gangveinettet har strekkene $A$ – $B$ , $A$ – $C$ , $B$ – $D$ , $C$ – $D$ , $C$ – $E$ , $D$ – $F$ ,
$E$ – $G$ , $F$ – $H$ og $G$ – $H$ — alle like lange og alle toveis. Finn antall strekk
fra $A$ til hver av de andre byggene.

Køen behandles i alfabetisk rekkefølge blant like kandidater, slik at sporingen
kan gjenskapes nøyaktig.

Steg	Tatt ut av køen	Nye noder oppdaget	Kø etter	avstand-tabell etter
1	A (avst. 0)	`B = 1`, `C = 1`	`B, C`	`A=0, B=1, C=1, D=∞, E=∞, F=∞, G=∞, H=∞`
2	B (avst. 1)	`D = 2`	`C, D`	`A=0, B=1, C=1, D=2, E=∞, F=∞, G=∞, H=∞`
3	C (avst. 1)	`E = 2`	`D, E`	`A=0, B=1, C=1, D=2, E=2, F=∞, G=∞, H=∞`
4	D (avst. 2)	`F = 3`	`E, F`	`A=0, B=1, C=1, D=2, E=2, F=3, G=∞, H=∞`
5	E (avst. 2)	`G = 3`	`F, G`	`A=0, B=1, C=1, D=2, E=2, F=3, G=3, H=∞`
6	F (avst. 3)	`H = 4`	`G, H`	`A=0, B=1, C=1, D=2, E=2, F=3, G=3, H=4`
7	G (avst. 3)	ingen	`H`	`A=0, B=1, C=1, D=2, E=2, F=3, G=3, H=4`
8	H (avst. 4)	ingen	`tom`	`A=0, B=1, C=1, D=2, E=2, F=3, G=3, H=4`

Sluttilstand — dette er svaret du leverer:

A=0, B=1, C=1, D=2, E=2, F=3, G=3, H=4

Se på steg 6 og 7. Node

H

oppdages fra

F

med avstand 4. Senere tas

G

ut
med avstand 3, og

G

har også en kant til

H

— men

H

er allerede oppdaget, og
en ny vei via

G

ville gitt

3 + 1 = 4

, altså det samme. BFS ser ikke engang på
den muligheten, og trenger ikke: første gang en node oppdages, er avstanden
allerede minimal.
Kontrollen: avstandene skal stige langs køen. Ser du at en node tas ut med
lavere avstand enn den forrige, har du gjort en feil i sporingen.

Fellenote. Fella her er å bruke denne metoden på en graf med vekter. Hadde

strekket $A$ – $C$ tatt ti minutter og $A$ – $B$ – $D$ tatt tre, ville BFS fortsatt

sagt at $C$ er «nærmere» enn $D$ . BFS teller kanter, ikke minutter.

📝Oppgave 1

(Innstegsoppgave, sjanger H — grafalgoritme, altså at du gjenkjenner problemet og
bruker riktig algoritme.) Et uvektet nett har kantene $A$ – $B$ , $A$ – $D$ , $B$ – $C$ ,
$C$ – $E$ , $D$ – $E$ , $E$ – $F$ , $F$ – $G$ , alle toveis.

a) Kjør BFS fra $A$ og oppgi avstanden til hver node.
b) Hvilken algoritme ville du brukt hvis kantene hadde hatt ulike, positive
vekter?

Løkke 2 — Dijkstra: alltid den nærmeste uferdige (ca. 18 min)

Nå koster strekkene forskjellig. Et bilnett mellom seks knutepunkter, med
kjøretider i minutter og enveiskjøring på alle strekk. Hvor lang tid tar det fra
$A$ til hvert av de andre?

Grunnideen i Dijkstras algoritme er én setning: ta alltid den uferdige noden med
lavest kjent avstand, og erklær den ferdig. Når du gjør det, kan ingen senere
oppdagelse gjøre den kortere — for enhver annen vei dit måtte gått gjennom en node
med høyere avstand, og alle kanter koster minst 0.

Den siste halvsetningen er hele forutsetningen: alle kanter må være
ikke-negative. Vi kommer tilbake til hva som skjer når de ikke er det.

Relaksering

u

Dijkstras algoritme

O((|V| + |E|)\log |V|)

📜Pseudokode-kontrakt: `Dijkstra`

Antagelser om representasjon. Grafen

G = (V, E)

er gitt som nabolister, der
G.naboer(v) gir parene (w, vekt) for hver kant v -> w. Alle vekter er
ikke-negative. avstand og forgjenger er arrayer indeksert på node.
Prioritetskøen PQ er en binær min-heap ordnet på avstand, med RemoveMin og
DecreaseKey i

O(\log |V|)

— se kap. 4.4.

Prebetingelse: ingen kantvekt er negativ.
Postbetingelse: avstand[v] er korteste avstand fra s til v for alle v,
og $\infty$ for noder som ikke kan nås.

Procedure Dijkstra(G, s)
  Input:  vektet graf G = (V, E) som nabolister, alle vekter >= 0; startnode s
  Output: avstand[v] = korteste avstand fra s til v, for alle v i V
  for hver v i V:
      avstand[v] = uendelig
      forgjenger[v] = ingen
  avstand[s] = 0
  PQ = min-heap med alle noder i V, ordnet paa avstand
  while PQ er ikke tom:
      u = PQ.RemoveMin()
      for hver (v, vekt) i G.naboer(u):
          if v er fortsatt i PQ and avstand[u] + vekt < avstand[v]:
              avstand[v] = avstand[u] + vekt
              forgjenger[v] = u
              PQ.DecreaseKey(v, avstand[v])
  return avstand, forgjenger

Invarianten i én setning: når en node tas ut av prioritetskøen, er avstand
til den noden endelig — ingen senere relaksering kan senke den, fordi enhver annen
vei dit må gå via en node som fortsatt ligger i køen og derfor har minst like høy
avstand.

Kjøretid: $O((|V| + |E|)\log |V|)$ . Tell operasjonene: $|V|$ kall på
RemoveMin, hvert $O(\log |V|)$ , gir $O(|V| \log |V|)$ . for-løkka kjøres én
gang per node, og går over den nodens naboliste — til sammen $|E|$ ganger — og
hver relaksering kan utløse en DecreaseKey à $O(\log |V|)$ , altså
$O(|E| \log |V|)$ . Summen er $O((|V| + |E|)\log |V|)$ .

Merk at det er en sum, ikke et produkt. Å skrive $O(|V| \cdot |E| \log |V|)$
er samme telleefeil som ved topologisk sortering: den indre løkka går over nabolista
til den ene noden, ikke over alle kanter.

✏️Eksempel 2: Dijkstra i bilnettet

Kjøretidene i minutter, alle enveiskjørte: A -> B 4, A -> C 2, C -> B 1,
B -> D 5, C -> D 8, C -> E 10, D -> E 2, D -> F 6, E -> F 3.

Finn korteste kjøretid fra $A$ til alle knutepunktene.

Prioritetskøen inneholder alle noder fra starten, med $\infty$ som avstand for
alle utenom $A$ . Kolonnen lengst til høyre viser køens innhold som heap-array
med indeks fra 0 — altså slik heapen faktisk lagrer det, ikke sortert. Element 0 er
alltid det minste; resten står i heap-orden.

Steg	Ferdig (tatt ut av køen)	Relakserte kanter	avstand-tabell etter	Prioritetskø etter (heap-array)
1	A (avstand 0)	`B: ∞ -> 4`, `C: ∞ -> 2`	`A=0, B=4, C=2, D=∞, E=∞, F=∞`	`(2, C), (∞, F), (4, B), (∞, D), (∞, E)`
2	C (avstand 2)	`B: 4 -> 3`, `D: ∞ -> 10`, `E: ∞ -> 12`	`A=0, B=3, C=2, D=10, E=12, F=∞`	`(3, B), (10, D), (12, E), (∞, F)`
3	B (avstand 3)	`D: 10 -> 8`	`A=0, B=3, C=2, D=8, E=12, F=∞`	`(8, D), (∞, F), (12, E)`
4	D (avstand 8)	`E: 12 -> 10`, `F: ∞ -> 14`	`A=0, B=3, C=2, D=8, E=10, F=14`	`(10, E), (14, F)`
5	E (avstand 10)	`F: 14 -> 13`	`A=0, B=3, C=2, D=8, E=10, F=13`	`(13, F)`
6	F (avstand 13)	ingen	`A=0, B=3, C=2, D=8, E=10, F=13`	`tom`

Sluttilstand — dette er svaret du leverer:

A=0, B=3, C=2, D=8, E=10, F=13

Se på steg 2. Kanten A -> B ga først avstand 4 til

B

. Men

C

tas ut før

B

, og fra

C

er det bare 1 minutt til

B

2 + 1 = 3 < 4

. Avstanden til

B

senkes, og forgjenger[B] blir

C

, ikke

A

. Den direkte kanten er ikke
korteste vei. Det er nettopp derfor du trenger algoritmen og ikke bare kan lese
av grafen.

Se på steg 3. Nå tas $B$ ut med avstand 3. Fra dette øyeblikket er 3 endelig —

og det er trygt, fordi alt annet i køen har avstand minst 3, og ingen kant kan

trekke fra.
Korteste vei til $F$ , lest ut av forgjengerne: $F$ kom fra $E$ , $E$ fra $D$ ,
$D$ fra $B$ , $B$ fra $C$ , $C$ fra $A$ . Veien er
A -> C -> B -> D -> E -> F med kostnad $2 + 1 + 5 + 2 + 3 = 13$ . Stemmer med
tabellen.

Kontrollen som fanger de fleste feil: avstandene på nodene som tas ut, skal
aldri synke. Her er de 0, 2, 3, 8, 10, 13 — stigende hele veien. Synker den, har du
enten regnet feil eller så har grafen en negativ kant.

Fellenote. Den vanligste feilen her er å avslutte for tidlig — å stoppe når
målnoden er oppdaget i stedet for når den er tatt ut av køen. I steg 2 er $F$
fortsatt $\infty$ , i steg 4 er den 14, og først i steg 5 blir den 13. Sensor ber om
avstandstabellen ved terminering.

📝Oppgave 2

Sjanger E

En rettet vektet graf har kantene A -> B 7, A -> C 3,
C -> B 2, B -> D 4, C -> D 9, B -> E 6, D -> E 1.

a) Kjør Dijkstra fra $A$ og oppgi hele avstandstabellen.
b) Hvilken vei går korteste rute til $E$ ?
c) Hvorfor er avstanden til $B$ ikke 7?

— naturlig pausepunkt —

Du har nå to av de fire radene i korteste-vei-matrisen: uvektet gir BFS, og
ikke-negative vekter gir Dijkstra. De to siste radene handler begge om det samme
spørsmålet: hva gjør vi når en kant kan være negativ?

Løkke 3 — når en kant kan være negativ (ca. 16 min)

Negative kanter høres kunstig ut i et veinett, men de er helt vanlige så snart
vekten er noe annet enn avstand: en transaksjon som gir gevinst, et
produksjonstrinn som frigjør kapasitet, et bytte som gir tilbake mer enn det
kostet.

Og de ødelegger Dijkstra. Ikke litt — helt.

✏️Eksempel 3: Dijkstra gir feil svar på én negativ kant

En graf har kantene A -> B 5, A -> C 6, C -> B −4 og B -> D 1. Grafen har
ingen sykel i det hele tatt, og altså heller ingen negativ sykel.

Kjør Dijkstra, kjør deretter Bellman-Ford, og forklar forskjellen.

Dijkstra først:

Steg	Ferdig (tatt ut av køen)	Relakserte kanter	avstand-tabell etter	Prioritetskø etter (heap-array)
1	A (avstand 0)	`B: ∞ -> 5`, `C: ∞ -> 6`	`A=0, B=5, C=6, D=∞`	`(5, B), (∞, D), (6, C)`
2	B (avstand 5)	`D: ∞ -> 6`	`A=0, B=5, C=6, D=6`	`(6, C), (6, D)`
3	C (avstand 6)	ingen	`A=0, B=5, C=6, D=6`	`(6, D)`
4	D (avstand 6)	ingen	`A=0, B=5, C=6, D=6`	`tom`

Dijkstra svarer A=0, B=5, C=6, D=6.
Bellman-Ford på samme graf. Algoritmen relakserer alle kanter, gjentatte
ganger, i

|V| - 1

runder:

Runde	Kanter som ga forbedring	avstand-tabell etter
1	`A -> B`: `∞ -> 5`, `A -> C`: `∞ -> 6`, `B -> D`: `∞ -> 6`, `C -> B`: `5 -> 2`	`A=0, B=2, C=6, D=6`
2	`B -> D`: `6 -> 3`	`A=0, B=2, C=6, D=3`
3	ingen endring	`A=0, B=2, C=6, D=3`

Bellman-Ford svarer A=0, B=2, C=6, D=3.

Sluttilstand — det riktige svaret:

A=0, B=2, C=6, D=3

Hvor Dijkstra gikk galt. I steg 2 ble

B

tatt ut med avstand 5 og erklært

ferdig. Men veien A -> C -> B koster $6 + (-4) = 2$ , altså mindre. Da $C$ ble tatt
ut i steg 3, var $B$ allerede ute av køen, og relakseringen ble aldri gjort.
Feilen forplantet seg videre til $D$ : 6 i stedet for 3.
Hvorfor invarianten brøt sammen. Dijkstras garanti hviler på at ingen kant kan
trekke fra: enhver vei via noder som fortsatt ligger i køen, må koste minst like

mye som den noden du tar ut. Med en negativ kant er det ikke sant lenger — en dyr

node kan lede til en billig kant.

Merk at grafen ikke engang har en sykel. Det er en utbredt misforståelse at

Dijkstra bare feiler ved negative sykler. Én enkelt negativ kant holder.
Fellenote. Fella er å bruke Dijkstra fordi grafen «ser grei ut». Kontrollen
tar to sekunder: finnes det en negativ vekt i det hele tatt? Hvis ja, er
Dijkstra utelukket — da er svaret Bellman-Ford, eller topologisk sortering hvis

grafen er en DAG.

Bellman-Ford

|V| - 1

Negativ sykel

|V|

Men det finnes en sak til, og den er den viktigste av dem alle på matrisen:
hva om grafen er en DAG?

I en DAG kan nodene ordnes slik at alle kanter peker framover. Går du gjennom
nodene i den rekkefølgen og relakserer utkantene deres, er hver node ferdig i
det du kommer til den — alt som kunne forbedret den, ligger bak deg. Da trenger du
ingen prioritetskø, og det spiller ingen rolle om noen vekter er negative.

📜Pseudokode-kontrakt: `DAGKortesteVei`

Antagelser om representasjon.

G = (V, E)

er en rettet asyklisk vektet
graf gitt som nabolister. Vektene kan være negative. avstand er et array
indeksert på node.

Prebetingelse: $G$ er en DAG. Postbetingelse: avstand[v] er korteste
avstand fra s til alle v som kan nås, og $\infty$ for resten.

Procedure DAGKortesteVei(G, s)
  Input:  vektet DAG G = (V, E) som nabolister, startnode s
  Output: avstand[v] = korteste avstand fra s til v
  topo = TopologiskSortering(G)
  for hver v i V:
      avstand[v] = uendelig
  avstand[s] = 0
  for hver u i topo, i rekkefolge:
      if avstand[u] er uendelig:
          fortsett med neste u
      for hver (v, vekt) i G.naboer(u):
          if avstand[u] + vekt < avstand[v]:
              avstand[v] = avstand[u] + vekt
              forgjenger[v] = u
  return avstand

Invarianten i én setning: når u behandles i topologisk rekkefølge, er alle
noder med en kant inn til u allerede behandlet, så avstand[u] kan ikke bli
lavere senere.

Kjøretid: $O(|V| + |E|)$ . Den topologiske sorteringen koster
$O(|V| + |E|)$ (se kap. 6.1), og løkka etterpå går gjennom
hver node én gang og hver kant én gang. To lineære pass etter hverandre er
fortsatt lineært.

Dette er raskere enn Dijkstra — $O(|V| + |E|)$ mot
$O((|V| + |E|)\log |V|)$ — og det tåler i tillegg negative vekter. Prisen er
forutsetningen: grafen må være asyklisk.

✏️Eksempel 4: Korteste vei i en vektet DAG med en negativ kant

Seks produksjonstrinn med kantene A -> B 3, A -> C 7, B -> C 2, B -> D 6,
C -> D 1, C -> E −3, D -> E 2, D -> F 5, E -> F 8. Kanten C -> E er
negativ fordi trinnet frigjør lagerplass.

Finn laveste totalkostnad fra $A$ til hvert trinn.

Steg 1 — topologisk rekkefølge. Alle kanter går fra en tidligere til en senere
bokstav, så grafen er en DAG, og A, B, C, D, E, F er en lovlig
topologisk rekkefølge.

Steg 2 — én gjennomgang i den rekkefølgen, med relaksering:

Steg	Node i topologisk rekkefølge	Relakserte kanter	avstand-tabell etter
1	A	`B: ∞ -> 3`, `C: ∞ -> 7`	`A=0, B=3, C=7, D=∞, E=∞, F=∞`
2	B	`C: 7 -> 5`, `D: ∞ -> 9`	`A=0, B=3, C=5, D=9, E=∞, F=∞`
3	C	`D: 9 -> 6`, `E: ∞ -> 2`	`A=0, B=3, C=5, D=6, E=2, F=∞`
4	D	`F: ∞ -> 11`	`A=0, B=3, C=5, D=6, E=2, F=11`
5	E	`F: 11 -> 10`	`A=0, B=3, C=5, D=6, E=2, F=10`
6	F	ingen	`A=0, B=3, C=5, D=6, E=2, F=10`

Sluttilstand — dette er svaret du leverer:

A=0, B=3, C=5, D=6, E=2, F=10

Se på $E$ . Avstanden til

E

er 2, som er lavere enn avstanden til både

C

(5) og

D

(6) — noe som er umulig i en graf med bare ikke-negative vekter.
Det er den negative kanten C -> E som gjør det:

5 + (-3) = 2

.
Og se hva Dijkstra ville gjort her: den ville tatt ut

E

… nei, den ville
først tatt ut

A

, så

B

(3), så

C

(5), og deretter

D

(6) — men i det

C

ble

tatt ut, ble $E$ satt til 2, altså lavere enn $C$ selv. En avstand som er lavere

enn den noden vi nettopp erklærte ferdig, bryter Dijkstras hele forutsetning. På

denne grafen hadde vi vært heldige og fått riktig svar likevel, men garantien er
borte, og på grafen i eksempel 3 var svaret feil. Du kan ikke bruke «det gikk
bra sist» som argument.

Kontrollen: hver node skal ha fått sin endelige verdi før den behandles i
rekkefølgen. Det følger av topologien, og det er derfor én gjennomgang holder.
Poengtrapp-notat. På en oppgave der grafen er en DAG, er
$O(|V| + |E|)$ det øverste trinnet. Dijkstra ( $O((|V| + |E|)\log |V|)$ ) er
korrekt hvis alle vekter er ikke-negative, men tregere, og gir færre poeng.
Bellman-Ford ( $O(|V| \cdot |E|)$ ) er riktigst av alle i den forstand at den
alltid virker — og gir minst poeng, fordi den er den tregeste.

📝Oppgave 3

Sjanger H

En vektet DAG har kantene A -> B 4, A -> C 2, C -> B −1,
B -> D 3, C -> D 8, D -> E 2.

a) Oppgi en topologisk rekkefølge.
b) Finn korteste avstand fra $A$ til alle nodene, ved å gå gjennom i den
rekkefølgen.
c) Hvorfor kan du ikke bruke Dijkstra her, og hvorfor spiller det ingen rolle
at grafen ikke har noen sykel?

📜Korteste-avstander-matrisen — de fire radene

Dette er det tryggeste Del 1-poenget i Del 6, og det kommer som en avkryssing
(sjanger F). Lær radene som en enhet:

Grafen er …	Bruk	Kjøretid
uvektet	bredde-først-søk (BFS)	$O(\lvert V \rvert + \lvert E \rvert)$
vektet DAG (asyklisk)	topologisk sortering, så én gjennomgang	$O(\lvert V \rvert + \lvert E \rvert)$
vektet uten negative kanter	Dijkstra med prioritetskø	$O((\lvert V \rvert + \lvert E \rvert)\log \lvert V \rvert)$
vektet med negative kanter, ingen negativ sykel	Bellman-Ford	$O(\lvert V \rvert \cdot \lvert E \rvert)$

Slik leser du matrisen riktig. Radene er ordnet fra raskest til tregest, og du
skal alltid velge den øverste raden som passer. En vektet DAG uten negative
kanter kan løses med Dijkstra — men topologisk sortering er raskere, og
poengtrappen belønner det raskeste korrekte svaret.
De to spørsmålene som avgjør raden:

1. Har kantene vekter i det hele tatt? Nei: bruk BFS.
2. Er grafen asyklisk? Ja: bruk topologisk sortering. Nei: finnes det en
negativ kant? Nei: bruk Dijkstra. Ja: bruk Bellman-Ford.
Merk at «ingen negativ sykel» er kravet til Bellman-Ford, ikke til Dijkstra.

Dijkstra krever at ingen kant er negativ. Å blande disse to er en fast felle,

og den koster hele avkryssingen.

📝Oppgave 4

Sjanger F

Fyll
inn den raskeste korrekte algoritmen og dens kjøretid for hver graftype.

a) Et uvektet sosialt nettverk.
b) En vektet, asyklisk arbeidsflyt der noen kanter har negativ vekt.
c) Et veinett med kjøretider i minutter, alle positive, med rundkjøringer
(altså sykler).
d) Et handelsnett med gevinster og tap på hver overføring, sykler finnes, men
ingen sykel gir netto gevinst.

Typiske feil

- Å bruke Dijkstra når en kant er negativ. Dette er den dyreste feilen i
kapitlet, og den er utbredt fordi mange husker forutsetningen som «ingen negativ
sykel». Det er Bellman-Fords krav. Dijkstra krever at ingen kant er negativ,
og feiler på en graf helt uten sykler, som i eksempel 3.
- Å kjøre Dijkstra fra hvert utgangspunkt når én reversert kjøring holder.
Dette er felle #1 i bokas feilregister — full/naiv gjennomgang der ett smart
grep var mulig — og den koster typisk halve poengsummen på Del 2. Se løkke 4.
- Å bruke BFS på en vektet graf. BFS teller kanter. To dyre kanter er «kortere»
enn tre billige, målt i antall — og det er som regel feil svar.
- Å stoppe Dijkstra når målnoden blir oppdaget. En node er ferdig først når den
er tatt ut av køen. I eksempel 2 hadde $F$ verdien 14 en stund før den ble
13.
- Å bruke Dijkstra på en vektet DAG. Korrekt (hvis vektene er ikke-negative),
men tregere enn nødvendig: $O((|V| + |E|)\log |V|)$ i stedet for
$O(|V| + |E|)$ . Poengtrappen straffer det.
- Å oppgi kjøretiden $O(|V| \cdot |E| \log |V|)$ for Dijkstra. Det er
telleefeilen der man ganger antall noder med antall kanter. Riktig svar er
$O((|V| + |E|)\log |V|)$ — en sum inni en logaritmefaktor.

Og den gjennomgående: å oppgi kjøretid uten å definere størrelsene. Skriv
$|V|$ for antall noder og $|E|$ for antall kanter, og si det. Bruker du $n$ uten
forklaring, er det felle #10, som det trekkes eksplisitt for.

Løkke 4 — trikset som skiller B fra A: snu grafen (ca. 14 min)

Nå kommer det grepet som oftest avgjør toppkarakteren på en korteste-vei-oppgave.

Situasjonen er alltid den samme i formen: du har flere mulige utgangspunkt og
ett mål, og spørsmålet er hvilket utgangspunkt som er nærmest målet. En
brannstasjon som skal velges, en av flere lagre som skal levere, en av flere
inngangsdører som skal brukes.

Den nærliggende løsningen er å kjøre Dijkstra fra hvert utgangspunkt og
sammenligne. Med $|U|$ utgangspunkt koster det $|U|$ Dijkstra-kjøringer, altså
$O(|U| \cdot (|V| + |E|)\log |V|)$ .

Den gode løsningen snur grafen. Avstanden fra $p$ til $t$ i $G$ er nøyaktig
det samme som avstanden fra $t$ til $p$ i den reverserte grafen $G^R$ . Så kjør
én Dijkstra, fra $t$ , i $G^R$ — og les av avstanden til alle utgangspunktene
på én gang.

✏️Eksempel 5: Eksamensnivå — hvilket utgangspunkt er nærmest?

Tre beredskapspunkter $P$ , $Q$ og $R$ skal vurderes. Et oppdrag skal utføres på
sted $T$ . Veinettet er enveiskjørt med kjøretider: P -> S 4, Q -> S 2,
Q -> M 7, R -> M 3, S -> T 5, M -> T 1.

Hvilket beredskapspunkt kommer raskest fram til $T$ ? Skriv en algoritme som løser
problemet generelt, med lavest mulig kjøretid.

Problemet navngitt. Dette er korteste vei til én bestemt node fra flere
mulige startnoder. Nøkkelobservasjonen er at «avstand fra

p

til

t

G

» er det
samme som «avstand fra

t

til

p

G^R

» — den samme veien, lest baklengs.

Antagelser om representasjon. $G = (V, E)$ er en rettet vektet graf gitt som
nabolister, med ikke-negative kjøretider. $U \subseteq V$ er mengden av
mulige utgangspunkt, og $t$ er målnoden. Vi kan bygge den reverserte grafen $G^R$
ved én gjennomgang av alle nabolistene, $O(|V| + |E|)$ .

Algoritmen.

Procedure NaermesteUtgangspunkt(G, U, t)
  Input:  rettet vektet graf G = (V, E), alle vekter >= 0;
          mengden U av mulige utgangspunkt; maalnoden t
  Output: den noden i U som har lavest kjoeretid til t, og selve kjoeretiden
  G_R = G med alle kanter snudd
  avstand = Dijkstra(G_R, t)
  beste = ingen
  for hver p i U:
      if beste er ingen or avstand[p] < avstand[beste]:
          beste = p
  return beste, avstand[beste]

Kjøring på tallene. Den reverserte grafen har kantene T -> S 5, T -> M 1,
S -> P 4, S -> Q 2, M -> Q 7, M -> R 3. Dijkstra fra $T$ :

Steg	Ferdig (tatt ut av køen)	Relakserte kanter	avstand-tabell etter	Prioritetskø etter (heap-array)
1	T (avstand 0)	`M: ∞ -> 1`, `S: ∞ -> 5`	`M=1, P=∞, Q=∞, R=∞, S=5, T=0`	`(1, M), (5, S), (∞, Q), (∞, R), (∞, P)`
2	M (avstand 1)	`Q: ∞ -> 8`, `R: ∞ -> 4`	`M=1, P=∞, Q=8, R=4, S=5, T=0`	`(4, R), (5, S), (8, Q), (∞, P)`
3	R (avstand 4)	ingen	`M=1, P=∞, Q=8, R=4, S=5, T=0`	`(5, S), (∞, P), (8, Q)`
4	S (avstand 5)	`P: ∞ -> 9`, `Q: 8 -> 7`	`M=1, P=9, Q=7, R=4, S=5, T=0`	`(7, Q), (9, P)`
5	Q (avstand 7)	ingen	`M=1, P=9, Q=7, R=4, S=5, T=0`	`(9, P)`
6	P (avstand 9)	ingen	`M=1, P=9, Q=7, R=4, S=5, T=0`	`tom`

Sluttilstand:

M=1, P=9, Q=7, R=4, S=5, T=0

Svaret:

R

er nærmest, med 4 minutter. Deretter

Q

med 7 og

P

med 9.
Kjøretid:

O((|V| + |E|)\log |V|)

— én reversering (

O(|V| + |E|)

), én
Dijkstra, og én gjennomgang av

U

(

O(|U|)

, som er høyst

O(|V|)

). Her er

|V|

antall veikryss og

|E|

antall veistrekk.
Hvorfor dette er lavest mulig, og hva den naive løsningen koster. Kjører du

Dijkstra fra hvert utgangspunkt, blir det $|U|$ kjøringer:

$O(|U| \cdot (|V| + |E|)\log |V|)$ . Med tre beredskapspunkter er det tre ganger

så mye arbeid; med hundre er det hundre ganger. Reverseringen fjerner faktoren

$|U|$ helt.
Poengtrappen på denne oppgavetypen er dokumentert eksplisitt i arkivet: den
reverserte løsningen er toppsvaret, $|U|$ Dijkstra-kjøringer er et korrekt

midtsvar, og det er nøyaktig den forskjellen som skiller A fra B. Felle #1
igjen: full gjennomgang der ett grep holdt.
Alternativet du også kan nevne: legg til en kunstig supernode $s^*$ med
kanter av vekt 0 inn til alle noder i $U$ , og kjør én Dijkstra fra $s^*$ . Det gir
korteste avstand fra «noe i $U$ » til $t$ i én kjøring — men det gir deg ikke

hvilket utgangspunkt som var best, uten å lese av forgjengerne. Reverseringen er
det reneste svaret her.

📝Oppgave 5

Sjanger H

I den reverserte grafen fra eksempel 5 fikk vi
M=1, P=9, Q=7, R=4, S=5, T=0.

a) Hvor lang tid tar det fra $Q$ til $T$ i den opprinnelige grafen, og
hvilken vei går ruten?
b) Et nytt beredskapspunkt $N$ legges til, med kanten N -> M av vekt 2. Blir
$N$ det nærmeste?
c) Hvorfor kan du svare på b) uten å kjøre Dijkstra på nytt fra bunnen?

📝Oppgave 6

Sjanger H, krevende

En leverandør har lagre i nodemengden $U$ og skal levere til
alle kunder i nodemengden $K$ . For hver kunde vil de vite hvilket lager som er
nærmest.

a) Hva koster det å kjøre reversert Dijkstra én gang per kunde?
b) Hva koster det å kjøre Dijkstra én gang per lager?
c) Hvilken av de to velger du, og hva er betingelsen?
d) Skriv løsningen for det tilfellet at $|U|$ er mye mindre enn $|K|$ .

📝Oppgave 7

Sjanger C

Marker sant eller usant, og begrunn hvert svar med én setning.

a) Dijkstra gir riktig svar så lenge grafen ikke har en negativ sykel.
b) Bellman-Ford kan brukes på enhver graf der Dijkstra kan brukes.
c) BFS gir korteste vei i en vektet graf der alle kanter har vekt 1.
d) Topologisk sortering kan brukes til korteste vei i en graf med sykler.
e) Dijkstra med binær prioritetskø er $O(|V| \cdot |E| \log |V|)$ .

Begrepsbank

Begrepsbanken er flashcard-/repetisjonsstoff — den gjentar det du nettopp har
lest. Hopp trygt over ved førstegangslesing; tidsanslaget for kapitlet gjelder
kjernestoffet.

Kortene her er kalibrert som eksamen tester dem: algoritme, kjøretid,
forutsetning. Fordi eksamen er hjelpemiddelfri, er dette puggematerialet.

Korteste-avstander-matrisen

O(|V| + |E|)

Dijkstras forutsetning

Ingen kantvekt får være negativ. Ikke «ingen negativ sykel» — det er Bellman-Fords krav. Grunnen ligger i invarianten: når en node tas ut av køen, er avstanden endelig fordi enhver annen vei dit må gå via en node med minst like høy avstand. En negativ kant kan trekke fra, og da faller argumentet.

Bellman-Fords kjøretid og forutsetning

O(|V| \cdot |E|)

Hvorfor

|V| - 1

runder i Bellman-Ford

|V| - 1

Korteste vei i vektet DAG

O(|V| + |E|)

Reversert Dijkstra

p

Supernode-trikset

U

Relaksering

\text{avstand}[v] = \min\bigl(\text{avstand}[v],\ \text{avstand}[u] + w(u, v)\bigr)

Dijkstras invariant

Når en node tas ut av prioritetskøen, er avstanden til den endelig . Begrunnelsen: enhver annen vei dit må gå gjennom en node som fortsatt ligger i køen, og den har minst like høy avstand — pluss en kant som ikke kan være negativ. Fjerner du ikke-negativitets-kravet, faller hele argumentet, og med det algoritmen.

`forgjenger`-arrayet

O(|V|)

BFS som korteste vei

O(|V| + |E|)

Prioritetskøens rolle i Dijkstra

O(\log |V|)

Negativ sykel

|V|

Enkeltkilde mot alle par

Alle fire algoritmene i dette kapitlet er enkeltkilde : én kjøring gir avstanden fra én startnode til alle andre. Vil du ha avstanden mellom alle par, må du kjøre en av dem én gang per node. Algoritmer laget spesielt for alle-par-problemet er ikke IN2010-pensum — se avgrensningen i kap. 7.3 .

Mønstergjenkjenning: «nærmeste kilde»

Ser du «hvilket av flere utgangspunkt er nærmest målet», er svaret én reversert Dijkstra, ikke én kjøring per utgangspunkt. Beslektede formuleringer: «hvilken av stasjonene kommer først fram», «hvilket lager skal levere», «hvilken inngang er nærmest». Alle har samme struktur: mange startnoder, ett mål.

Å stoppe Dijkstra tidlig

t

Uoppnåelige noder

\infty

Poengtrappen på korteste vei

O(|V| + |E|)

Repetisjon — kapitlet på ett kort

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Universitetet i Oslo. Dette er ikke offisielt studiemateriell. Les mer.