Korteste vei fra én til alle

Gitt en vektet rettet graf og en startnode $s$: hva er den korteste avstanden fra $s$ til hver av de andre nodene? Énkilde-korteste-vei-problemet har flere algoritmer som ser ulike ut, men deler én eneste operasjon i kjernen — kantoppdatering. Forskjellen mellom dem ligger ikke i hva de gjør, men i hvilke grafer de tåler og i hvilken rekkefølge de oppdaterer.

Varianter av problemet

Korteste-vei-problemet finnes i flere innpakninger, men de henger tett sammen:

Vi løser altså én-til-alle: bygg et korteste-vei-tre med rot i $s$, der stien fra $s$ til hver node $v$ i treet er en korteste vei.

Strukturen til korteste veier

Hele teorien hviler på én observasjon:

Dette er nettopp den optimale delstrukturen som åpner for dynamisk programmering — og som vi snart ser bokstavelig talt er DP når grafen er en DAG. Hver algoritme holder et estimat $d[v] \ge \delta(s, v)$ og presser det nedover mot $\delta(s, v)$ ved hjelp av kanter.

Kantoppdatering — den felles kjernen

Den ene operasjonen som driver alle énkilde-algoritmene er Relax:

Forskjellen mellom algoritmene er rekkefølgen kantene relakseres i:

• Bellman-Ford relakserer alle kanter, $V-1$ ganger — den bryr seg ikke om rekkefølge og tåler derfor negative kanter.
• DAG-Shortest-Paths relakserer kantene i topologisk rekkefølge — én gang hver holder.
• Dijkstra relakserer kantene ut fra den nærmeste ubesøkte noden — grådig, og krever ikke-negative vekter.

Negative kanter og negative sykler

Bellman-Ford utnytter nettopp dette: etter $V-1$ runder med full relaksering er alle korteste avstander funnet (en enkel vei har høyst $V-1$ kanter). Klarer en ekstra, $V$-te runde fortsatt å forbedre et estimat, må det finnes en nåbar negativ sykel — og algoritmen rapporterer det. Kjøretiden er

— $V-1$ runder à $O(E)$ relakseringer.

Korteste vei i en DAG er dynamisk programmering

Er grafen en DAG (rettet og asyklisk), finnes ingen sykler i det hele tatt — heller ikke negative. Da kan vi gjøre noe mye raskere enn Bellman-Ford: sorter nodene topologisk og relakser de utgående kantene én gang per node, i den rekkefølgen.

Når vi behandler $v$, er alle noder som kan nå $v$ allerede ferdigbehandlet — så $d[v]$ er endelig idet vi kommer dit. Dette er ikke en tilfeldighet: det er en DP der delproblemene er «korteste vei til $v$», og den topologiske ordningen er nettopp en gyldig evalueringsrekkefølge for avhengighetene $d[v] = \min_{(u,v)} \{ d[u] + w(u,v) \}$. Hele kjøringen er $O(V + E)$ — like raskt som en traversering.

Dijkstras algoritme

Når alle vektene er ikke-negative kan vi være grådige. Dijkstra holder en mengde $Q$ av uoppgjorte noder og plukker gjentatte ganger ut den med minst nåværende estimat, gjør den opp, og relakserer dens utgående kanter. Nøkkelen er at med ikke-negative vekter er estimatet til den nærmeste ubesøkte noden allerede endelig — ingen senere kant kan korte det ned.

def dijkstra(adj, source):
  d = {v: INF for v in adj}
  d[source] = 0
  Q = set(adj)                  # uoppgjorte noder
  while Q:
      u = min(Q, key=lambda v: d[v])   # extract-min
      Q.remove(u)
      for v, w in adj[u]:
          if d[u] + w < d[v]:           # relax
              d[v] = d[u] + w
              parent[v] = u
  return d

Den grådige korrektheten avhenger fullstendig av ikke-negative vekter. Med en binær min-haug som prioritetskø — én extract-min per node og én decrease-key per kant — blir kjøretiden

og med Fibonacci-haug $O(E + V \lg V)$. Algoritmen er strukturelt en vektet slektning av bredde-først-søk: BFS bruker en FIFO-kø fordi alle kanter «koster» 1, mens Dijkstra bruker en prioritetskø fordi kantene har ulik vekt.

Sjekk deg selv