Dijkstra-Algorithmus Rechner
Gewichteter Graph · Kürzeste Distanzen ab Startknoten · Schrittweise Algorithmus-Verfolgung · Pfad-Visualisierung
Beispiel: A B 5 = Kante von A nach B mit Gewicht 5. Knotennamen können Buchstaben oder Zahlen sein.
Geben Sie ein positives Gewicht für eine Kante ein, 0 für keine Kante. Die Diagonale ist immer 0. Bearbeiten Sie die Knotenbezeichnungen in den grünen Kopfzeilen.
Schnellbeispiele
Einfaches Netzwerk
5 Knoten · 7 Kanten · ungerichtet
Stadtstraßen
8 Knoten · gerichtet · S → T
Klassischer Graph
6 Knoten · ungerichtet · Startknoten 1
Kürzester Weg zum Ziel
Gesamtdistanz
Pfadlänge
Kürzeste-Distanz-Tabelle
| Knoten | Distanz ab Startknoten | Kürzester Weg |
|---|
Adjazenzmatrix-Ansicht (Pfadkanten hervorgehoben)
Schrittweise Algorithmus-Verfolgung
| Schritt | Besuchter Knoten | Aktualisierte Distanzen |
|---|
Was ist der Dijkstra-Algorithmus?
Der Dijkstra-Algorithmus ist einer der bekanntesten Algorithmen der Informatik. Er wurde 1956 vom niederländischen Informatiker Edsger W. Dijkstra entwickelt und 1959 veröffentlicht. Er löst das Single-Source-Shortest-Path-Problem für einen gewichteten Graphen mit nicht-negativen Kantengewichten. Ausgehend von einem Startknoten berechnet der Algorithmus den kostengünstigsten Weg von diesem Startknoten zu jedem anderen Knoten im Graphen.
Der Algorithmus ist ein klassisches Beispiel für eine gierige (greedy) Strategie: In jedem Schritt wird der unbesuchte Knoten mit der aktuell kleinsten bekannten Distanz ausgewählt und anschließend genutzt, um die bekannten Distanzen zu seinen Nachbarknoten zu verbessern. Dieser Vorgang wird als Relaxation bezeichnet.
Wie der Dijkstra-Algorithmus funktioniert
- Alle Distanzen werden auf Unendlich initialisiert, außer der Startknoten, der auf 0 gesetzt wird.
- Alle Knoten werden als unbesucht markiert. Alle Knoten werden in eine Menge unbesuchter Knoten aufgenommen.
- Der unbesuchte Knoten u mit der kleinsten vorläufigen Distanz wird ausgewählt.
- Für jeden unbesuchten Nachbarn v von u wird
alt = dist[u] + weight(u, v)berechnet. - Falls
alt < dist[v], wirddist[v] = altaktualisiert undprev[v] = ugespeichert. - u wird als besucht markiert (aus der Menge der unbesuchten Knoten entfernt).
- Wiederholen ab Schritt 3, bis alle Knoten besucht sind oder der Zielknoten erreicht wurde.
Um den Weg zu einem beliebigen Knoten zu rekonstruieren, wird das prev[]-Array vom Zielknoten zurück bis zum Startknoten verfolgt.
Beispiel für den Dijkstra-Algorithmus
Betrachten wir das Beispiel „Einfaches Netzwerk" mit 5 Knoten (A–E) und folgenden Kanten: A-B=4, A-C=2, B-C=1, B-D=5, C-D=8, C-E=10, D-E=2. Ausgehend von A:
| Schritt | Besuchend | dist[A] | dist[B] | dist[C] | dist[D] | dist[E] |
|---|---|---|---|---|---|---|
| Start | — | 0 | ∞ | ∞ | ∞ | ∞ |
| 1 | A | 0 | 4 | 2 | ∞ | ∞ |
| 2 | C | 0 | 3 | 2 | 10 | 12 |
| 3 | B | 0 | 3 | 2 | 8 | 12 |
| 4 | D | 0 | 3 | 2 | 8 | 10 |
| 5 | E | 0 | 3 | 2 | 8 | 10 |
Endgültige kürzeste Distanzen ab A: B=3 (A→C→B), C=2 (A→C), D=8 (A→C→B→D), E=10 (A→C→B→D→E).
Analyse der Zeitkomplexität
| Implementierung | Zeitkomplexität | Speicher | Am besten geeignet für |
|---|---|---|---|
| Array / naiv | O(V²) | O(V) | Dichte Graphen |
| Binärer Heap | O((V + E) log V) | O(V + E) | Dünnbesetzte Graphen |
| Fibonacci-Heap | O(E + V log V) | O(V + E) | Theoretisches Optimum |
Dieser Rechner verwendet die O(V²)-Array-Implementierung, die für Graphen mit bis zu 15 Knoten vollkommen effizient ist.
Wann sollte man den Dijkstra-Algorithmus statt anderer Algorithmen verwenden?
| Algorithmus | Negative Gewichte | Einzelner Startknoten | Alle Knotenpaare | Komplexität |
|---|---|---|---|---|
| Dijkstra | Nein | Ja | Nein | O(V²) oder O(E log V) |
| Bellman-Ford | Ja | Ja | Nein | O(VE) |
| Floyd-Warshall | Ja | Nein | Ja | O(V³) |
| A*-Suche | Nein | Ja (einzelnes Ziel) | Nein | O(E log V) mit Heuristik |
| BFS | Entfällt (ungewichtet) | Ja | Nein | O(V + E) |
Anwendungen in der Praxis
- GPS-Navigation: Ermittlung der schnellsten oder kürzesten Route zwischen zwei Orten in einem Straßennetz.
- Netzwerk-Routing: Internet-Router verwenden Varianten des Dijkstra-Algorithmus (OSPF-Protokoll), um den besten Pfad für Datenpakete zu bestimmen.
- Pfadfindung in Spielen: NPC-Charaktere in Videospielen navigieren mithilfe des Dijkstra-Algorithmus oder seiner heuristischen Variante A* durch das Gelände.
- Logistik & Lieferkette: Optimierung von Lieferrouten zur Minimierung von Distanz oder Kosten.
- Soziale Netzwerke: Ermittlung der kürzesten Verbindungskette zwischen zwei Personen (Trennungsgrade).
- Flugroutenplanung: Berechnung der kostengünstigsten Reiseroute zwischen zwei Flughäfen.
Häufig gestellte Fragen
Was ist der Dijkstra-Algorithmus?
Welche Einschränkungen hat der Dijkstra-Algorithmus?
Wie hoch ist die Zeitkomplexität des Dijkstra-Algorithmus?
Wie gebe ich einen Graphen in den Rechner ein?
Von Nach Gewicht ein. Zum Beispiel erzeugt A B 5 eine Kante zwischen A und B mit Gewicht 5. Knotennamen können beliebige Buchstaben oder Zahlen sein. Alternativ können Sie den Tab „Adjazenzmatrix" für eine visuelle Rastereingabe nutzen.