Dijkstra-Algorithmus für gewichtete kürzeste Wege
Dijkstra bestimmt von einem Startknoten aus kürzeste Wege in gewichteten Graphen, wenn alle Kantengewichte nichtnegativ sind.
Ansehen kostenlos · Karteikarten oder Multiple-Choice-Test · übernehmen ab Essential
Formel
w und δ sind additive Pfadkosten; V Knoten und E Kanten; mit binärer Prioritätswarteschlange und Adjazenzlisten O((|V|+|E|) log |V|).
Variablen & Einheiten
| Symbol | Bedeutung | Einheit |
|---|---|---|
| Endlicher gerichteter oder ungerichteter Graph | Knoten und Kanten | |
| Nichtnegatives Gewicht der Kante von u nach v | Kosten je Kante | |
| Startknoten und Zielknoten | Knoten | |
| Kleinste Summe der Kantengewichte auf einem Weg von s nach v | Pfadkosten | |
| Aktuell beste bekannte obere Schranke für δ(s,v) | Pfadkosten |
LaTeX
\delta(s,v)=\min_{p:s\leadsto v}\sum_{e\in p}w(e),\quad d(v)\gets\min(d(v),d(u)+w(u,v))
Eigene schematische Darstellung von Quanta
Kostenlos mit Quanta-Konto. Dein Download bleibt nach der Registrierung bereit.
Herleitung & Hintergrund
Initialisiere d(s)=0 und alle übrigen Distanzen mit ∞. Für jede Kante (u,v) prüft die Relaxation d(v)←min(d(v),d(u)+w(u,v)), ob der Weg über u besser ist. Eine Min-Prioritätswarteschlange wählt jeweils den noch offenen Knoten mit dem kleinsten vorläufigen Wert. Weil alle Kantengewichte nichtnegativ sind, kann dessen Distanz danach endgültig feststehen. Negative Kanten verletzen diese Begründung; dafür ist Dijkstra ungeeignet. Mit binärer Heap-Prioritätswarteschlange und Adjazenzlisten beträgt die Laufzeit O((|V|+|E|)log|V|); andere Warteschlangen ändern die Laufzeit.
Prüfungs-Blueprint
Gültigkeitsbereich
Initialisiere d(s)=0 und alle übrigen Distanzen mit ∞. Für jede Kante (u,v) prüft die Relaxation d(v)←min(d(v),d(u)+w(u,v)), ob der Weg über u besser ist. Eine Min-Prioritätswarteschlange wählt jeweils den noch offenen Knoten mit dem kleinsten vorläufigen Wert. Weil alle Kantengewichte nichtnegativ sind, kann dessen Distanz danach endgültig feststehen. Negative Kanten verletzen diese Begründung; dafür ist Dijkstra ungeeignet. Mit binärer Heap-Prioritätswarteschlange und Adjazenzlisten beträgt die Laufzeit O((|V|+|E|)log|V|); andere Warteschlangen ändern die Laufzeit.
Herleitung in Schritten
Dijkstra hält beste bekannte Distanzen fest und verbessert sie durch Kantenrelaxation.
- 1Setze d(s)=0 und alle anderen Distanzen auf ∞.
- 2Wähle den noch offenen Knoten mit der kleinsten vorläufigen Distanz.
- 3Relaxiere seine ausgehenden Kanten; bei nichtnegativen Gewichten ist seine Distanz danach endgültig.
Umstellen
Kantenrelaxation
Aktualisiere d(v) nur, wenn der Weg über u kürzer ist; Dijkstra setzt nichtnegative Kantengewichte voraus.
Aufgabenvariante
Gerichteter Graph mit Kantengewichten: s→a(2), s→b(5), a→b(1), a→t(6), b→t(2). Führe Dijkstra von s nach t aus.
Nach s: d(a)=2, d(b)=5.
Über a sinkt d(b) auf 3.
Über b wird d(t)=5.
Der Weg s→a→b→t kostet 2+1+2=5; die Alternativen kosten 8 und 7.
Typische Fehler
Den zuerst entdeckten Weg zu einem Knoten sofort als endgültig festschreiben.
Erst beim Entnehmen des kleinsten vorläufigen Werts finalisieren; das setzt nichtnegative Kanten voraus.
Klausurkontext
- Wegstrecken, Routingkosten und nichtnegative Gewichte in Netzwerken als kürzeste Pfade berechnen.
Formelcluster
Graphen und Algorithmen
Dijkstra bestimmt von einem Startknoten aus kürzeste Wege in gewichteten Graphen, wenn alle Kantengewichte nichtnegativ sind.
Rechenbeispiel
Kanten: s→a mit 2, s→b mit 5, a→b mit 1, a→t mit 6 und b→t mit 2. Nach s erhält a den Wert 2 und b zunächst 5. Über a sinkt b auf 3; über b sinkt t auf 5. Der kürzeste Weg s→a→b→t kostet 2+1+2=5. Probe: Der direkte Weg s→a→t kostet 8 und s→b→t kostet 7.
Anwendungsgebiete
Wegstrecken, Routingkosten und nichtnegative Gewichte in Netzwerken als kürzeste Pfade berechnen.
Rechenbeispiel: Dijkstra-Algorithmus für gewichtete kürzeste Wege
Eine typische Aufgabe Schritt für Schritt: Dijkstra-Algorithmus für gewichtete kürzeste Wege (Kürzester Pfad: min Σw(e); Relaxation: d(v) ← min(d(v), d(u)+w(u,v))).
- 1
Aufgabe
Gerichteter Graph mit Kantengewichten: s→a(2), s→b(5), a→b(1), a→t(6), b→t(2). Führe Dijkstra von s nach t aus.
Rechenweg
Nach s: d(a)=2, d(b)=5.
Über a sinkt d(b) auf 3.
Über b wird d(t)=5.
Der Weg s→a→b→t kostet 2+1+2=5; die Alternativen kosten 8 und 7.
Häufige Fragen: Dijkstra-Algorithmus für gewichtete kürzeste Wege
Was beschreibt Dijkstra-Algorithmus für gewichtete kürzeste Wege?+
Die Beziehung \delta(s,v)=\min_{p:s\leadsto v}\sum_{e\in p}w(e),\quad d(v)\gets\min(d(v),d(u)+w(u,v)) beschreibt Dijkstra bestimmt von einem Startknoten aus kürzeste Wege in gewichteten Graphen, wenn alle Kantengewichte nichtnegativ sind. Im Beispiel Kanten: s→a mit 2, s→b mit 5, a→b mit 1, a→t mit 6 und b→t mit 2. Sie gilt unter den im Hintergrund genannten Voraussetzungen. Gültigkeitsgrenze: Initialisiere d(s)=0 und alle übrigen Distanzen mit ∞. Für jede Kante (u,v) prüft die Relaxation d(v)←min(d(v),d(u)+w(u,v)), ob der Weg über u besser ist. Eine Min-Prioritätswarteschlange wählt jeweils den noch offenen Quelle: MIT OpenCourseWare 6.006, Lecture 13: Dijkstra’s Algorithm.
Wie gehe ich bei einer Rechnung vor?+
Schreibe zuerst die gesuchte Größe und alle gegebenen Werte mit ihren Bezeichnungen auf. Setze sie in \delta(s,v)=\min_{p:s\leadsto v}\sum_{e\in p}w(e),\quad d(v)\gets\min(d(v),d(u)+w(u,v)) ein und prüfe, ob die Einheiten zusammenpassen. Das Beispiel Kanten: s→a mit 2, s→b mit 5, a→b mit 1, a→t mit 6 und b→t mit 2. Nach s erhält a den Wert 2 und b zunächst 5. Über a sinkt b auf 3; über b sinkt t auf 5. Der kürzeste Weg s→a→b→t kostet 2+1+2=5. Probe: Der direkte Weg s→a→t kostet 8 und s→b→t kostet 7. liefert eine Rechenprobe: Werte Formel und Ergebnis müssen dieselbe Größenordnung und Bedeutung ergeben; runde erst am Ende. Gültigkeitsgrenze: Initialisiere d(s)=0 und alle übrigen Distanzen mit ∞. Für jede Kante (u,v) prüft die Relaxation d(v)←min(d(v),d(u)+w(u,v)), ob der Weg über u besser ist. Eine Min-Prioritätswarteschlange wählt jeweils den noch offenen Quelle: MIT OpenCourseWare 6.006, Lecture 13: Dijkstra’s Algorithm.
Welche Annahme darf ich nicht übersehen?+
Die Formel gilt nur, wenn die Größen so definiert sind wie in der Quelle und im Hintergrundtext. Prüfe insbesondere Randfälle, Messbedingungen und ob ein Näherungszeichen statt Gleichheit gemeint ist. Ein formal korrektes Einsetzen kann trotzdem fachlich falsch sein, wenn diese Voraussetzungen verletzt werden oder die betrachtete Population beziehungsweise Systemgrenze wechselt. Gültigkeitsgrenze: Initialisiere d(s)=0 und alle übrigen Distanzen mit ∞. Für jede Kante (u,v) prüft die Relaxation d(v)←min(d(v),d(u)+w(u,v)), ob der Weg über u besser ist. Eine Min-Prioritätswarteschlange wählt jeweils den noch offenen Quelle: MIT OpenCourseWare 6.006, Lecture 13: Dijkstra’s Algorithm.
Welche Einheiten und Größen gehören dazu?+
Die angegebene Einheit lautet: w und δ sind additive Pfadkosten; V Knoten und E Kanten; mit binärer Prioritätswarteschlange und Adjazenzlisten O((|V|+|E|) log |V|).. Vor dem Einsetzen müssen alle Werte auf ein konsistentes Einheitensystem gebracht werden; Anzahlen, Prozentangaben und dimensionslose Verhältnisse sind dabei nicht austauschbar. Die Variablenliste benennt die Rolle jedes Symbols. Einheitenkontrolle erkennt viele Fehler, ersetzt aber nicht die Prüfung, ob die Formelannahmen erfüllt sind. Gültigkeitsgrenze: Initialisiere d(s)=0 und alle übrigen Distanzen mit ∞. Für jede Kante (u,v) prüft die Relaxation d(v)←min(d(v),d(u)+w(u,v)), ob der Weg über u besser ist. Eine Min-Prioritätswarteschlange wählt jeweils den noch offenen Quelle: MIT OpenCourseWare 6.006, Lecture 13: Dijkstra’s Algorithm.
Wann ist ein Vergleich mit graphsuche-bfs-dfs-kuerzeste-wege und big-o-notation sinnvoll?+
Ein Vergleich hilft, wenn beide Größen dieselbe Aufgabe beantworten, aber unterschiedliche Eigenschaften betonen. Berichte Definition, Eingabedaten, Schwelle oder Aggregation zusammen mit dem Zahlenwert. Die Quelle MIT OpenCourseWare 6.006, Lecture 13: Dijkstra’s Algorithm. stützt die hier verwendete Definition; bei anderen Konventionen können Ergebnisse abweichen. Verwende die Kennzahl deshalb passend zum konkreten Lern- oder Analyseziel. Gültigkeitsgrenze: Initialisiere d(s)=0 und alle übrigen Distanzen mit ∞. Für jede Kante (u,v) prüft die Relaxation d(v)←min(d(v),d(u)+w(u,v)), ob der Weg über u besser ist. Eine Min-Prioritätswarteschlange wählt jeweils den noch offenen Quelle: MIT OpenCourseWare 6.006, Lecture 13: Dijkstra’s Algorithm.
Quanta-Prüfungsset
Kuratiertes Prüfungsset für "Dijkstra-Algorithmus für gewichtete kürzeste Wege":
Frage (Vorderseite)
Welche Formel beschreibt Dijkstra-Algorithmus für gewichtete kürzeste Wege?
Antwort in deinem Set
Frage (Vorderseite)
Welcher typische Fehler passiert bei Kürzester Pfad: min Σw(e); Relaxation: d(v) ← min(d(v), d(u)+w(u,v))?
Antwort in deinem Set
+ 9 weitere Karten: Einheiten, Variablen, Herleitung, Beispiel, Klausuraufgabe
Das Formelset enthält 11 Karten. Nach der Übernahme kannst du sie prüfen und lernen; deine Bewertungen bestimmen die weiteren Wiederholungen.
Fachquellen und weiterführende Literatur
Die Liste nennt Fachquellen und weiterführende Literatur. Eine Seiten- oder Abschnittsnummer steht dabei, wenn sie Teil der Literaturangabe ist; es handelt sich nicht um wörtliche Zitate.
Verwandte Formeln
Weitere Formeln: Algorithmen, Zahlendarstellung und Kryptographie
Dijkstra-Algorithmus für gewichtete kürzeste Wege prüfungssicher behalten
Erstelle ein kuratiertes FSRS-Prüfungsset für Kürzester Pfad: min Σw(e); Relaxation: d(v) ← min(d(v), d(u)+w(u,v)): Formelabruf, Variablen, Herleitung, Umstellung, Beispiel, typische Fehler und Klausurkontext.
Kuratiertes Formelset · LaTeX · FSRS Spaced Repetition · übernehmen ab Essential