Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Teil 1·Erklärung
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Google Maps macht es 8 Milliarden Mal am Tag: berechne die schnellste Route von A nach B. Der Standard-Algorithmus dafür ist Dijkstra. Er findet in einem gewichteten Graphen den kürzesten Pfad von einem Startknoten zu allen anderen. Klausur-Pflicht in 14/17 WInf-Algorithmen-Klausuren.
Klausur-Tipp: Bei Dijkstra-Aufgaben IMMER eine Tabelle mit dist + prev anlegen und in jeder Iteration explizit aktualisieren. Markiere den aktuellen Knoten, die Nachbarn die geprüft werden, und die tatsächlichen Updates. Spart Verwirrung und gibt Teilpunkte bei Rechenfehlern.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
Google Maps macht es 8 Milliarden Mal am Tag: berechne die schnellste Route von A nach B. Der Standard-Algorithmus dafür ist Dijkstra. Er findet in einem gewichteten Graphen den kürzesten Pfad von einem Startknoten zu allen anderen. Klausur-Pflicht in 14/17 WInf-Algorithmen-Klausuren.
Dijkstra: Vom Startknoten ausgehend nimmst du immer den noch unbesuchten Knoten mit der kürzesten bekannten Entfernung, fügst ihn zum "fertigen" Set hinzu und aktualisierst von dort aus die Entfernungen zu seinen Nachbarn.
4
A ─────── B
│ \ │
│ \ 2 │ 5
1 │ \ │
│ \ │
│ \ │
C ─────── D
3
Kanten: A-B (4), A-C (1), A-D (2), B-D (5), C-D (3).
Start: A. Frage: kürzeste Entfernung zu jedem Knoten?
| Knoten | dist | Vorgänger |
|---|---|---|
| A | 0 | — |
| B | 4 | A |
| C | 1 | A |
| D | 2 | A |
Aber: A → D (2) ist kürzer als A → C → D (1 + 3 = 4). Dijkstra findet das automatisch.
Setup:
dist[v] = ∞ für alle Knoten außer Startdist[start] = 0Loop:
u mit kleinstem dist[u]u als "fertig"v von u (noch nicht fertig):
alt = dist[u] + gewicht(u, v)alt < dist[v]: dist[v] = alt, vorgänger[v] = u (Relax-Schritt)Bis PQ leer oder Ziel erreicht.
dijkstra(graph, start):
for v in graph.nodes:
dist[v] = infinity
prev[v] = null
dist[start] = 0
pq = PriorityQueue(all nodes with dist as key)
while pq not empty:
u = pq.extractMin()
for each neighbor v of u:
alt = dist[u] + weight(u, v)
if alt < dist[v]:
dist[v] = alt
prev[v] = u
pq.decreaseKey(v, alt)
| Implementierung | Komplexität |
|---|---|
| Array (naiv) | O(V²) |
| Binary Heap | O((V + E) log V) |
| Fibonacci-Heap | O(E + V log V) (theoretisch beste) |
Standard-Klausur-Antwort: O((V + E) log V) mit Binary Heap.
Dijkstra funktioniert NUR bei nicht-negativen Kantengewichten.
Bei negativen Kanten: nutze Bellman-Ford (O(V · E)). Bei negativen Zyklen ist "kürzester Weg" überhaupt nicht definiert (du könntest unendlich oft im Zyklus laufen).
Klausur-Falle: Manche Aufgaben tarnen negative Gewichte als "Profit", "Nutzen", "Diskont" — vorsichtig lesen.
Dijkstra speichert nur Distanzen + Vorgänger. Für den eigentlichen Pfad zu Knoten z:
path = []
current = z
while current != null:
path.prepend(current)
current = prev[current]
Du folgst dem Vorgänger-Pfeil rückwärts vom Ziel zum Start.
BFS ist im Prinzip Dijkstra mit Kantengewicht 1.
1. Tabelle führen: dist + prev für jeden Knoten. Bei jedem Schritt aktualisieren. Klausur-Standard.
2. Aus PQ den Knoten mit min(dist) ziehen. Wichtig: BEKANNTE Distanz, nicht "geschätzt".
3. Relax-Schritt: dist[v] = min(dist[v], dist[u] + w(u,v)). Update nur wenn neuer Weg kürzer.
4. O((V+E)log V) mit Binary Heap. Standard-Komplexität.
5. NUR nicht-negative Gewichte. Bei negativen → Bellman-Ford.
1. Knoten zweimal aus PQ ziehen. Sobald ein Knoten "fertig" markiert ist, NICHT mehr aktualisieren. Manche Implementierungen ohne decreaseKey ziehen einen Knoten mehrfach — dann ignorieren wenn schon fertig.
2. Negative Gewichte ignoriert. Bei der Klausur IMMER prüfen: "sind alle Kantengewichte ≥ 0?" Wenn nein, Dijkstra falsch.
3. Pfad-Rekonstruktion umgekehrt. Du folgst prev rückwärts vom Ziel — vergiss nicht zu reversen oder vorne anzufügen.
4. Dijkstra mit Tiefensuche verwechseln. Dijkstra ist eine Form von Greedy + Priority-Queue + Best-First-Search, NICHT Tiefensuche (DFS).
5. Dist statt Vorgänger updaten. Beim Relax-Schritt MUSS sowohl dist[v] als auch prev[v] aktualisiert werden, sonst geht die Pfad-Info verloren.
Geh durch das klassische Dijkstra-Beispiel Schritt für Schritt. Pro Schritt siehst du:
dist- und prev-WertenProbier verschiedene Start-Knoten aus.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Bei Dijkstra-Aufgaben IMMER eine Tabelle mit dist + prev anlegen und in jeder Iteration explizit aktualisieren. Markiere den aktuellen Knoten, die Nachbarn die geprüft werden, und die tatsächlichen Updates. Spart Verwirrung und gibt Teilpunkte bei Rechenfehlern.
6 Aufgaben zu Algorithmus-Schritten, Komplexität, Voraussetzungen.
Klausurfragen mit Lösungen (6)
Antwort: Kürzester Pfad in gewichteten Graphen (nicht-negative Gewichte)
Erklärung: Dijkstra: Single-Source-Shortest-Path in gewichteten Graphen mit nicht-negativen Kantengewichten. Von einem Start zu allen anderen Knoten. Negative Gewichte → Bellman-Ford.
Antwort: O((V + E) log V)
Erklärung: Mit Binary Heap: `O((V + E) log V)`. Extract-min ist `O(log V)` und passiert V-mal, decrease-key ist `O(log V)` und passiert E-mal. Mit Fibonacci-Heap: `O(E + V log V)` (theoretisch besser).
Antwort: Falsch
Erklärung: FALSCH. Dijkstra braucht nicht-negative Kantengewichte. Bei negativen kann ein Knoten 'fertig' markiert werden, obwohl ein späterer kürzerer Weg über einen negativen Edge existiert. Für negative Kanten: Bellman-Ford.
Typ: Wahr/Falsch
Antwort: Distanz eines Nachbarn updaten, wenn neuer Weg kürzer ist
Erklärung: Relax-Schritt: wenn dist[u] + w(u,v) < dist[v], dann dist[v] = dist[u] + w(u,v) und prev[v] = u. Lockert die obere Schranke der Distanz zu v. Klassiker-Begriff.
Richtige Antworten: Findet kürzesten Pfad von einem Start zu allen anderen Knoten; Funktioniert mit nicht-negativen Kantengewichten; BFS ist ein Spezialfall (alle Gewichte = 1); Wird mit Priority Queue effizient implementiert
Erklärung: Richtig: Single-Source-Shortest-Path, nicht-negative Kanten, BFS-Spezialfall, Priority Queue. Falsch: speichert nur prev-Vorgänger (Pfad-Rekonstruktion am Ende rückwärts); negative Zyklen sind nicht definiert für kürzeste Wege.
Typ: Multi-Select
Zuordnungen:
Erklärung: Shortest-Path-Algorithmus-Familie. Dijkstra/Bellman-Ford für gewichtet, BFS für ungewichtet, A* für zielgerichtete Suche mit Heuristik.
Typ: Zuordnung
Klausurfragen mit Lösungen (6)
Antwort: 5
Erklärung: A → C (2) → B (1) → D (2) = 5. Vergleiche: A → C → D = 2 + 3 = 5, A → B → D = 5 + 2 = 7, A → C → B → D = 2 + 1 + 2 = 5. Minimum: 5.
Typ: Zahlen-Eingabe
Antwort: Fibonacci Heap — O(E + V log V)
Erklärung: Theoretisch optimal: Fibonacci Heap O(E + V log V). Bei dichten Graphen (E ≈ V²) ist auch der naive Array-Ansatz mit O(V²) konkurrenzfähig. Praktisch wird oft Binary Heap genutzt (gut + einfacher).
Antwort: Wahr
Erklärung: RICHTIG. Wenn alle Kanten Gewicht 1 haben, ist die kürzeste Distanz einfach die Kantenanzahl — genau was BFS findet. BFS ist effizienter (`O(V + E)`) als Dijkstra, weil es keine Priority Queue braucht (FIFO-Queue reicht).
Typ: Wahr/Falsch
Antwort: Bei negativen Kantengewichten
Erklärung: Negative Kanten brechen Dijkstras Korrektheit-Argument: ein 'fertiger' Knoten könnte nochmal kürzer erreichbar werden über eine negative Kante. Für negative Gewichte: Bellman-Ford. Zyklen ohne negative Kanten sind ok.
Lösungen pro Lücke:
Erklärung: Standard-Vokabular Dijkstra. Gewichtet + nicht-negativ, Extract-Min nach dist, Relax-Schritt für Updates.
Typ: Lückentext
Richtige Reihenfolge:
Erklärung: Standard-Dijkstra-Loop. Initialisierung → PQ → Extract-Min → Relax-Schritt für alle Nachbarn → Wiederholung bis fertig.
Typ: Reihenfolge