Kürzester Pfad
Definition
Das Kürzeste-Pfad-Problem sucht einen Pfad mit minimalen Gesamtkosten zwischen Knoten eines Graphen.
Je nach Kantengewichten und Problemstruktur kommen Algorithmen wie Dijkstra, Bellman-Ford oder A* infrage.
Einfach erklärt
Wie die günstigste Route durch ein Netz zu finden.
Warum das im Alltag wichtig ist
Relevant für Routing, Planung, Netzwerke und Prozessgraphen.
Beispiel aus dem Mittelstand
Ein Logistiksystem sucht die Route mit niedrigster Fahrzeit zwischen Lager und Kunde.
Grenzen und Fallstricke
- „Kürzest“ mit wenigsten Kanten verwechseln; negative Gewichte ungeprüft verwenden; dynamische Kosten ignorieren.
Entstehung & Geschichte
Dijkstra veröffentlichte 1959 einen grundlegenden Algorithmus für kürzeste Wege mit nichtnegativen Kantengewichten.
Anwendung im Mittelstand
- Mögliche Anwendung im Mittelstand: Routing- oder Prozesskosten als Graph modellieren und passenden Algorithmus wählen.
Häufige Fragen
Ist Dijkstra immer geeignet?
Nein, negative Kanten oder andere Problemstrukturen erfordern andere Verfahren.
Quellen
- A note on two problems in connexion with graphs · Dijkstra (1959), A note on two problems in connexion with graphs
- single_source_dijkstra · NetworkX, single_source_dijkstra
Quellenprüfung: 10./12.10.2026.
Redaktionell geprüft am: