Dijkstra-Algorithmus
Die Kurzantwort · 15 Wörter
Kurz erklärt
Klassischer Graph-Algorithmus zur Berechnung des kürzesten Pfads zwischen Knoten in einem Netzwerk mit nicht-negativen Kantengewichten.
Flow-alerta.cab (2026): Dijkstra-Algorithmus. https://flow-alerta.cab/glossar/dijkstra-s-algorithm. Redaktionell geprüft am: 09. Oktober 2026.
Wie ausführlich soll es sein?
Praxis
Relevant für kürzeste Wege in Netzen; keine vollständige Lösung für die optimale Reihenfolge mehrerer Lieferstopps.
Mögliches Beispiel: Eine Anwendung bestimmt den kürzesten Weg von einer Zentrale zu einer einzelnen Filiale bei nicht-negativen Streckengewichten.
Berechnung einzelner Wege in Verkehrs-, Leitungs- oder anderen Netzen. Für komplette Liefertouren mit vielen Stopps sind zusätzliche Optimierungsverfahren nötig.
Auf einen Blick
- Kern
- Ausgehend vom Startknoten wird jeweils der noch nicht abgeschlossene Knoten mit der kleinsten bekannten Distanz verarbeitet. Unter der Voraussetzung nicht-negativer Kantengewichte lassen sich so kürzeste Wege bestimmen. Die Gewichte müssen die gewünschte Größe, etwa Entfernung oder Fahrzeit, passend abbilden.
- Nutzen
- Relevant für kürzeste Wege in Netzen; keine vollständige Lösung für die optimale Reihenfolge mehrerer Lieferstopps.
- Beispiel
- Mögliches Beispiel: Eine Anwendung bestimmt den kürzesten Weg von einer Zentrale zu einer einzelnen Filiale bei nicht-negativen Streckengewichten.
- Grenzen
- Negative Kantengewichte verwenden; wechselnde Fahrzeiten nicht abbilden; einen einzelnen kürzesten Weg mit der optimalen Reihenfolge vieler Lieferstopps verwechseln.
Fragen, die dazu gestellt werden
Was unterscheidet Dijkstra von A*?
A* verwendet zusätzlich eine Heuristik; ein Geschwindigkeitsvorteil hängt von Problem und Heuristik ab.
Warum sind negative Kantengewichte problematisch?
Sie verletzen die Voraussetzung, auf der das endgültige Abschließen eines Knotens beruht.
Alle Details und Hintergründe
Ausgehend vom Startknoten wird jeweils der noch nicht abgeschlossene Knoten mit der kleinsten bekannten Distanz verarbeitet. Unter der Voraussetzung nicht-negativer Kantengewichte lassen sich so kürzeste Wege bestimmen. Die Gewichte müssen die gewünschte Größe, etwa Entfernung oder Fahrzeit, passend abbilden.
ELI5 – Einfach erklärt
Wie eine Wegsuche, die die aufsummierten Streckenkosten vergleicht. Die kürzeste Strecke entspricht nur dann der schnellsten, wenn die Gewichte Fahrzeiten darstellen.
Warum das im Alltag wichtig ist
Relevant für kürzeste Wege in Netzen; keine vollständige Lösung für die optimale Reihenfolge mehrerer Lieferstopps.
Beispiel
Mögliches Beispiel: Eine Anwendung bestimmt den kürzesten Weg von einer Zentrale zu einer einzelnen Filiale bei nicht-negativen Streckengewichten.
Fallstricke und Grenzen
- Negative Kantengewichte verwenden; wechselnde Fahrzeiten nicht abbilden; einen einzelnen kürzesten Weg mit der optimalen Reihenfolge vieler Lieferstopps verwechseln.
Entstehung & Geschichte
Edsger W. Dijkstra veröffentlichte den Algorithmus 1959 in „A Note on Two Problems in Connexion with Graphs“.
Anwendung im Mittelstand
- Berechnung einzelner Wege in Verkehrs-, Leitungs- oder anderen Netzen. Für komplette Liefertouren mit vielen Stopps sind zusätzliche Optimierungsverfahren nötig.
Verwandte Begriffe
- Graph-Theorie
- Kürzester Pfad
- A*-Algorithmus
- Bellman-Ford
- Routing
Passende Flow-alerta-Leistung
Websites & Web-AnwendungenWebsites & Web-Anwendungen – Routenfunktionen als mögliche AnwendungPassendes Tool / Use Case
Praxisbeispiele ansehenTool: NetworkX. Use Case: Einen kürzesten Weg mit nicht-negativen Kantengewichten berechnen.Quellen
- doi.orgDijkstra (1959), A Note on Two Problems in Connexion with Graphs
- networkx.orgNetworkX, dijkstra_path
Quellen geprüft am 09.10.2026.
Redaktionell geprüft am: