Begreper & referanser
Alle nøkkelbegrepene, formlene og referansene fra Korteste vei fra én kilde, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.
Begreper
Sentrale begreper fra kapittelet med korte definisjoner.
En sti mellom to noder med minst mulig total kantvekt. betegner korteste avstand fra til .
Operasjonen som strammer inn avstandsestimatet til en node hvis en kant gir en kortere vei dit.
En peker fra hver node til den forrige noden på korteste vei, slik at selve veien kan rekonstrueres.
Relakser alle kanter ganger; takler negative kanter og oppdager negative sykler.
Velger gjentatt den nærmeste uavklarte noden med en prioritetskø. Krever ikke-negative kantvekter.
En sykel med negativ total vekt; da finnes ingen korteste vei, fordi man kan gå rundt og bli stadig billigere.
I en asyklisk graf gir relax i topologisk rekkefølge korteste vei i lineær tid, også med negative kanter.
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
Relax
Kjerneoperasjonen i alle korteste-vei-algoritmer: hvis veien via er kortere enn dagens estimat for , stram inn estimatet.
Trekantulikheten for korteste vei
Korteste avstand til er aldri lengre enn korteste avstand til pluss kanten fra til . Grunnlaget for at relax er korrekt.
Bellman-Ford
Relakser alle kanter ganger. Takler negative kanter og oppdager negative sykler hvis en -te runde fortsatt strammer inn et estimat.
Dijkstra med binærhaug
Plukker gjentatt den nærmeste uavklarte noden fra en prioritetskø og relakser kantene dens. Forutsetter ikke-negative kantvekter.
DAG-korteste-vei
I en rettet asyklisk graf gir det å relaxe kantene i topologisk rekkefølge korteste vei i lineær tid — selv med negative kanter.
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Forklare relax-operasjonen og hvorfor avstandsestimatet alltid er et øvre tak som synker mot riktig verdi
- 02Begrunne hvorfor Bellman-Ford trenger V-1 runder og hvordan en ekstra runde avslører en negativ sykel
- 03Forklare hvorfor Dijkstra krever ikke-negative kantvekter og hva som går galt ellers
- 04Velge mellom DAG-korteste-vei, Bellman-Ford og Dijkstra ut fra om grafen er asyklisk og om vektene kan være negative