CMD + K
Algoritmer og datastrukturer
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
1 / 30Init: dist[A] = 0, alle andre avstander ∞.
Avstand & forgjengerdist[v] · prev[v]
A
B
C
D
E
F
dist
0
∞
∞
∞
∞
∞
prev
·
·
·
·
·
·
—
Relaterte kapitler