Oversikt

Korteste vei-problemer handler om a finne stien med lavest totalvekt mellom to noder i en vektet graf. Valg av algoritme avhenger av om grafen har negative vekter, om den er rettet eller urettet, og om vi onsker korteste vei fra en kilde til alle andre noder (single-source) eller mellom alle par (all-pairs).

Dijkstras algoritme

Dijkstra finner korteste vei fra en startnode s til alle andre noder i en graf med ikke-negative vekter. Algoritmen bruker en prioritetsko (min-heap) og en greedy-strategi: i hvert steg velger den noden med lavest tentativ avstand. Kjoretid med binaer heap: O((|V| + |E|) * log(|V|)). Med en botte-ko (bucket queue) kan kjoretiden forbedres til O(|V| + |E|) nar vektene er sma heltall.

Pa H2024 (DNT-oppgaven) ble det bedt om a finne utfartsstedet med lavest avstand til et reisemal. Et vanlig triks er a reversere kantene og kjore Dijkstra fra malet -- da finner du avstand fra malet til alle noder, og kan velge det beste utfartsstedet. Alternativt kan man kjore Dijkstra fra alle utfartssteder, men det er mindre effektivt.

Bellman-Ford

Bellman-Ford finner korteste vei fra en kilde til alle andre noder, og handterer negative vekter. Algoritmen relakserer alle kanter |V|-1 ganger. Etter dette kan man sjekke for negative sykler ved a relaksere en gang til -- hvis noen avstand forbedres, finnes det en negativ sykel. Kjoretid: O(|V| * |E|).

Pa H2022 ble det eksplisitt spurt om kjoretiden til Bellman-Ford -- den er O(|V| * |E|). Bellman-Ford er tregere enn Dijkstra, men nodvendig nar vektene kan vaere negative.

BFS for uvektede grafer

I uvektede grafer (eller grafer der alle kanter har lik vekt) er BFS tilstrekkelig for a finne korteste sti. BFS gir korteste sti malt i antall kanter. Kjoretid: O(|V| + |E|). Pa H2023 (Blindern-problemet) ble BFS nevnt som losning for korteste sti i tunnelsystemet (et tre).

Reversering av graf

Et viktig triks er a reversere alle kanter i grafen og kjore korteste vei-algoritme fra malnode i stedet for a kjore fra alle mulige startnoder. Pa H2024 er dette den effektive losningen: reverser G, kjor Dijkstra fra t, og finn utfartsstedet s i U med lavest avstand.

Eksempel 1: Dijkstra med prioritetsko

Procedure Dijkstra(G, w, s):
  dist = ny ordbok (alle noder -> uendelig)
  dist[s] = 0
  pq = ny min-heap
  pq.insert((0, s))
  while pq er ikke tom:
    (d, u) = pq.removeMin()
    if d > dist[u]: continue  // foreldet oppforing
    for each nabo v av u:
      ny_dist = dist[u] + w(u, v)
      if ny_dist < dist[v]:
        dist[v] = ny_dist
        pq.insert((ny_dist, v))
  return dist

Eksempel 2: Reverser graf og kjor Dijkstra (H2024-stil)

Procedure FindBestStart(G, w, U, t):
  // Reverser alle kanter
  G_rev = ny tom graf med samme noder som G
  for each kant (u, v) i G:
    G_rev.leggTilKant(v, u, w(u, v))
  // Kjor Dijkstra fra t i reversert graf
  dist = Dijkstra(G_rev, w_rev, t)
  // Finn utfartssted med lavest avstand
  best = null
  for each s i U:
    if dist[s] < dist[best]:
      best = s
  return best

Studieguide: Korteste vei-algoritmer

Studieguide: Korteste vei-algoritmer