Korteste vei fra én kilde

Én kilde, alle mål

Et navigasjonssystem som regner ut raskeste rute hjem løser et korteste-vei-problem. Vi har en vektet, rettet graf — kryssene er noder, veistrekkene er kanter, og vekten er kjøretid — og vi vil finne korteste vei fra én startnode $s$ til hver eneste andre node. Vekten på en sti er summen av kantvektene, og vi skriver $\delta (s,v)$ for den minste mulige stivekten fra $s$ til $v$.

Hvorfor regne ut til alle noder når vi kanskje bare vil ett sted? Fordi det viser seg at det ikke er billigere å finne korteste vei til ett enkelt mål enn til alle. Algoritmene bygger uansett opp avstandene lag for lag utover fra kilden, og målet ditt ligger et eller annet sted i det laget. Resultatet er ikke bare avstandene, men et helt korteste-vei-tre: fra hver node peker en forgjengerpeker bakover mot kilden, slik at selve veien kan leses ut ved å følge pekerne hjem.

I figuren står hver node merket med sin korteste avstand fra S. De grønne kantene er treet av forgjengerpekere. Merk at korteste vei til A ikke går direkte S→A (vekt 10), men omveien S→C→A med samlet vekt 5+3 = 8. Det er hele utfordringen: en kortere vei kan gå via en omvei.

Relax: den ene operasjonen alt hviler på

Alle algoritmene i dette kapittelet er bygd av den samme byggeklossen, relax. Vi holder for hver node $v$ et estimat $d[v]$ på avstanden, satt til $\infty$ i starten og $d[s]=0$ for kilden. Estimatet er alltid et øvre tak på den sanne avstanden $\delta (s,v)$, og det synker monotont mot riktig verdi etter hvert som vi oppdager kortere veier.

Å relakse kanten fra $u$ til $v$ betyr: sjekk om veien til $u$, etterfulgt av kanten $(u,v)$, er bedre enn dagens estimat for $v$. Hvis den er det, stram inn. ƒrelax

RELAX(u, v):
  hvis d[u] + vekt(u, v) < d[v]:
      d[v] = d[u] + vekt(u, v)
      forelder[v] = u

Korrektheten hviler på trekantulikheten: den korteste avstanden til $v$ er aldri lengre enn avstanden til $u$ pluss kanten fra $u$ til $v$. ƒtrekantulikheten for korteste vei Forskjellen mellom algoritmene er bare i hvilken rekkefølge de relakser kantene. Det er det hele.

Bellman-Ford: brutalt, men takler negative kanter

Den enkleste strategien er å ikke være smart i det hele tatt: relaks alle kantene, om og om igjen. bellman-ford gjør nettopp dette $V-1$ ganger.

BELLMAN-FORD(G, s):
  for hver node v: d[v] = uendelig, forelder[v] = ingen
  d[s] = 0
  gjenta |V| - 1 ganger:
      for hver kant (u, v) i G:
          RELAX(u, v)
  for hver kant (u, v) i G:          # ekstra runde: sjekk negativ sykel
      hvis d[u] + vekt(u, v) < d[v]:
          meld fra: negativ sykel finnes

Hvorfor er $V-1$ runder nok? En korteste vei kan ha høyst $V-1$ kanter, fordi en sti uten gjentatte noder ikke kan være lengre. Etter runde 1 er alle korteste veier med én kant funnet, etter runde 2 alle med to kanter, og slik forplanter riktig avstand seg én kant per runde. Etter $V-1$ runder er alt funnet. ƒbellman-ford

Den store styrken er at Bellman-Ford takler negative kantvekter.

Her er kanten B→C negativ med vekt $-6$. Selv om S→B koster mer enn S→A i utgangspunktet (5 mot 4), gir den negative kanten at korteste vei til C går via B: $5+(-6)=-1$, bedre enn via A der $4+2=6$. En grådig algoritme som låser avstanden til A tidlig ville bommet — men Bellman-Ford relakser alt på nytt og fanger rabatten.

Når korteste vei ikke finnes

Negative kanter åpner en farlig dør: hva om en sykel har negativ total vekt? Da finnes ingen negativ sykel-fri korteste vei, for vi kan gå rundt sykelen igjen og igjen og bli stadig billigere — avstanden går mot $-\infty$. Korteste vei er da udefinert.

Bellman-Ford oppdager dette gratis. Etter de $V-1$ rundene skal ingen kant kunne strammes inn mer hvis avstandene er ferdige. Kjører vi én ekstra runde og en kant fremdeles lar seg relakse, må det finnes en negativ sykel et sted, og algoritmen melder fra i stedet for å returnere et meningsløst svar. Det er den ekstra løkka nederst i pseudokoden over.

DAG-korteste-vei: lineær tid i en asyklisk graf

Hvis grafen er rettet og asyklisk — en DAG — kan vi gjøre det mye raskere enn Bellman-Ford, selv med negative kanter. Trikset er rekkefølgen: relaks kantene i dag-korteste-vei, altså i topologisk rekkefølge.

DAG-SHORTEST-PATHS(G, s):
  sorter nodene topologisk
  for hver node v: d[v] = uendelig, forelder[v] = ingen
  d[s] = 0
  for hver node u i topologisk rekkefølge:
      for hver nabo v av u:
          RELAX(u, v)

Når vi behandler en node $u$ i topologisk orden, er alle kanter inn til $u$ allerede relaksert, fordi de kom fra noder tidligere i ordenen. Da er $d[u]$ ferdig, og vi kan trygt relaksere kantene ut. Hver kant relakses nøyaktig én gang, så det hele går i lineær tid. ƒdag-korteste-vei En DAG kan ikke ha sykler i det hele tatt, så negative sykler er et ikke-problem her.

Dijkstra: raskest, men krever ikke-negative vekter

Når alle vektene er ikke-negative — som faktiske kjøretider eller avstander — kan vi gjøre noe smartere enn å relakse alt på nytt. dijkstra plukker gjentatt den uavklarte noden med lavest estimat, erklærer den ferdig, og relakser bare kantene dens.

DIJKSTRA(G, s):
  for hver node v: d[v] = uendelig, forelder[v] = ingen
  d[s] = 0
  Q = alle noder i en prioritetskø på d
  S = {}                              # ferdige noder
  mens Q ikke er tom:
      u = EXTRACT-MIN(Q)
      S = S + {u}
      for hver nabo v av u:
          RELAX(u, v)                 # senker nøkkelen til v i Q

Den avgjørende observasjonen er at når en node trekkes ut som den nærmeste uavklarte, er estimatet dens allerede den endelige avstanden. Med ikke-negative vekter kan ingen senere oppdaget vei være kortere, for enhver omvei må gå via en node som er minst like langt unna. Derfor trenger Dijkstra aldri å revurdere en ferdig node — det er det som gjør den rask. Men nettopp denne antakelsen ryker med negative kanter: da kan en billig kant senere senke en avstand vi trodde var fastlåst, og Dijkstra gir feil svar. For negative kanter må du tilbake til Bellman-Ford.

Med en binærhaug koster de $V$ uttrekkene og de $E$ nøkkel-senkningene hver $O(\lg V)$. ƒdijkstra med binærhaug Det gir $O((V+E)\lg V)$, langt bedre enn Bellman-Fords $\Theta (V\cdot E)$. På eksempelgrafen i den første figuren tar Dijkstra nodene i rekkefølgen S (0), C (5), D (7), A (8), B (9), E (9) — hver gang den nærmeste som ennå ikke er ferdig.

Velg riktig verktøy

Tre algoritmer, ett problem, og valget styres av grafen. Er grafen asyklisk, gir DAG-korteste-vei svaret i lineær tid uansett fortegn på vektene. Har du negative kanter i en graf med sykler, må du bruke Bellman-Ford, som på kjøpet forteller deg om en negativ sykel gjør problemet uløselig. Er alle vektene ikke-negative, er Dijkstra det klart raskeste valget. Felles for alle tre er relax-operasjonen og trekantulikheten — det er bare rekkefølgen kantene strammes inn i som skiller dem.