Dijkstras korteste vej-algoritme

It A · STX · A-niveau · Datastrukturer og algoritmer

💻 Dijkstras korteste vej-algoritme

Dijkstras algoritme (Edsger Dijkstra 1956, publiceret 1959) — finder korteste vej fra én knude til alle andre i en VÆGTET graf med IKKE-NEGATIVE kanter. Én af algoritmernes mest fundamentale.

Anvendelser

GPS-navigation (Google Maps), netværk-routing (OSPF protocol), spil (path-finding for AI), telefonopkald-routing.

Grundidé: greedy algorithm. Start fra start-knude. Find altid den UBESØGTE knude med MINDST kendt afstand. Opdater naboers afstande hvis vej via denne knude er kortere.

Algoritme-trin:

1. Markér start-knude med distance 0, alle andre med ∞.

2. Vælg den ubesøgte knude med mindst distance.

3. For hver nabo, beregn alternativ distance gennem nuværende knude. Hvis kortere end kendt, opdater.

4. Marker nuværende knude som besøgt.

5. Gentag indtil alle besøgt.

Tidskompleksitet: med priority queue (min-heap): O((V+E) log V). Med simple array: O(V²).

Begrænsning: virker IKKE med negative kant-vægte. Brug Bellman-Ford (O(V·E)) hvis negative vægte.

Eksempel: byer A, B, C, D. Veje: A-B (4), A-C (2), B-C (1), B-D (5), C-D (8). Find korteste fra A til D.

1. A=0, alle andre ∞.

2. Vælg A. Opdater: B=4, C=2.

3. Vælg C (mindst). Opdater: B = min(4, 2+1) = 3. D = 2+8 = 10.

4. Vælg B. D = min(10, 3+5) = 8.

5. Vælg D. Færdig. Korteste vej A→D = 8 (via A-C-B-D? eller A-C-D? Faktisk A-C-D = 10, A-B-D = 9, A-C-B-D = 8. ✓). *A\-algoritme**: udvidelse af Dijkstra med heuristik. Bruges i spil og navigation. f(n) = g(n) + h(n), hvor g = afstand f

Læringsmål

• Redegøre for Dijkstras algoritme til at finde korteste vej i en graf
• Implementere algoritmen på et simpelt graf-eksempel
• Diskutere algoritmens begrænsninger ved negative kantvægte

Sådan kan du arbejde med emnet

• Kør Dijkstras algoritme på en graf med 5 noder og find den korteste vej fra node A til alle andre
• Forklar, hvad der er Dijkstras tidskompleksitet, og hvad der afgør den
• Diskutér, hvad der er begrænsningen ved Dijkstras algoritme, og hvornår Bellman-Ford er nødvendig

Arbejd iterativt med prototyper og dokumentation. Test, evaluér og dokumentér.