Algoritmer og datastrukturerHjem

CMD + K

Tilbake til Algoritmer og datastrukturer

TDT4120 · Grafer

Korteste vei

Relaks kanter til ingen avstand kan krympe mer. Dijkstra finaliserer grådig — raskt, men stoler på at avstander bare vokser. Vipp én kant negativ og se Bellman–Ford holde seg rett der Dijkstra brister.

Rettet, vektet graf · kilde A
KV-treRelaksererForeldet
21-3245310A∞B∞C∞D∞E∞F
1 / 30Init: dist[A] = 0, alle andre avstander ∞.
Avstand & forgjengerdist[v] · prev[v]
A
B
C
D
E
F
dist
0
∞
∞
∞
∞
∞
prev
·
·
·
·
·
·
—

Lær mer

d(v) er korteste kjente avstand fra kilden og prev[v] er forelderen i korteste-vei-treet. Dijkstra er grådig og rask, men forutsetter ikke-negative kanter. Bellman–Ford relakserer alle kanter |V|−1 ganger og takler negative kanter (og oppdager negative sykler).

Velg «Negativ kant» og kjør Dijkstra: den låser en node så snart den tas ut av køen og ser aldri på den igjen — men en senere negativ kant kunne gitt en kortere vei. Bellman–Ford gir fasiten, og avviket lyser rødt på slutten.

Relaterte kapitler

10Korteste vei fra én kilde