Kürzeste Wege erklärt
Kürzeste Wege fragen, wie sich in einem Netz die beste Route finden lässt, meist in einem Straßennetz. Das Beispiel dieser Linie sind Lieferwege: kleine Netze, die sich noch überblicken lassen, Stadtnetze beliebiger Größe und in einigen Stücken ein echtes Straßennetz aus Toronto. In fast jedem Stück wächst das Beispiel, bis das Verfahren an seine Grenze kommt. In der Praxis sind kürzeste Wege meist eine Voraussetzung für die Tourenplanung, nicht deren eigentliches Ziel.
Jedes Stück greift eine Schwäche des vorigen auf: von der Breitensuche, die Kosten ignoriert, über Dijkstra, der blind in alle Richtungen sucht, bis zu Verfahren, die vorrechnen (Contraction Hierarchies, Hub Labeling), mit negativen Kanten umgehen (Bellman-Ford, Floyd-Warshall, Johnson), zwei Ziele zugleich abwägen (Mehrkriterien-Routing, RAPTOR) oder die Uhrzeit berücksichtigen. Fast jede Demo misst auch, wann das Verfahren nichts bringt: Contraction Hierarchies gewinnen im Toronto-Netz und verlieren im Zufallsnetz.
In short: Covers shortest-path algorithms: breadth-first search, Dijkstra, contraction hierarchies, Bellman-Ford, Johnson's algorithm, multi-criteria routing and RAPTOR. Interactive demos grow the example, including a real road network, until each method hits its limit.
Hintergrund zum Thema: Tourenplanung.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.
Zuletzt aktualisiert:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Zum Nachlesen: erst einfach, dann fachlich
Der Dijkstra-Algorithmus verständlich erklärt
Warum Dijkstra die Orte nacheinander endgültig festlegen darf, immer den mit den bisher geringsten Kosten, und warum das mit negativen Kosten nicht mehr stimmt: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Die zwölf Stücke im Überblick
Die Breitensuche ist die Wurzel: Sie zählt Kanten statt Kosten. Dijkstra behebt das, sucht aber blind in alle Richtungen und verträgt keine negativen Kanten. Aus diesen Schwächen wachsen die Äste: Die bidirektionale Suche geht von beiden Enden aus, Contraction Hierarchies rechnen vor, damit nicht jede Anfrage von vorn beginnt, und tragen zwei Fortsetzungen, Hub Labeling (die Suche vorwegnehmen) und Customizable Contraction Hierarchies (Kosten wechseln). Bellman-Ford erlaubt negative Kanten, Floyd-Warshall liefert alle Paare, und Johnson führt beides zusammen (Doppelrahmen).
Zwei weitere Äste ändern, was ein Weg kostet: Beim Mehrkriterien-Routing gibt es zwei Kosten und damit eine Pareto-Front statt einer besten Route, beim zeitabhängigen Routing hängen die Kosten von der Uhrzeit ab. RAPTOR, die Fahrplanauskunft in Runden, übernimmt die Pareto-Front aus dem Mehrkriterien-Routing und ersetzt Kanten durch Fahrten; zu Dijkstra steht es als Kontrast (Runden statt Warteschlange).
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- Gegenstück: derselbe Zweck, andere Bauweise (kein Fix)
- übernimmt nur eine Idee
- Zusammenfluss mehrerer Stränge
Der Doppelrahmen zeigt den Zusammenfluss von Bellman-Ford und Floyd-Warshall in Johnson. Gestrichelte Doppelpfeile stehen für einen Kontrast statt eines Fixes, der gepunktete Pfeil für eine übernommene Idee.
Verwandt in anderen Linien
- Heuristische Baumsuche — A* steht bewusst nur einmal, in der A*-Demo der Heuristische-Baumsuche-Linie: es ist Dijkstra mit Richtungsinformation (mit h ≡ 0 reproduziert es die Expansionsreihenfolge von Uniform-Cost, also von Dijkstra, exakt). Dort wird auch gemessen, wie viel der Vorsprung der Luftlinie auf Vierer-Rastern tatsächlich bringt (1,38x weniger Expansionen als Uniform-Cost im Standardfall).
- Spannbäume — Der billigste Spannbaum ist nicht der Baum der kürzesten Wege: die Kruskal-Demo vergleicht den MST mit dem Dijkstra-Baum ab dem Depot (Baukosten gegen Umwege).
- Netzwerkfluss — Kürzeste Wege sind der Baustein der Netzwerkfluss-Linie: Successive Shortest Paths rechnet je Runde einen kürzesten Weg im Restgraphen, mit Potenzialen wie in Johnson statt Bellman-Ford (539 gegen 953 durchsuchte Kanten), und auch das Pricing der Column Generation ist ein Dijkstra mit Preisen.
- Matching-Algorithmen — Auch die Ungarische Methode der Matching-Linie hat eine Dijkstra-Sicht: Sie wechselt jede Runde auf einen kürzesten Weg über reduzierte Kosten, kostet dafür aber 1698 gegen 140 durchsuchte Kanten bei den Verbesserungswegen ab Greedy (Reichweite 40).
- Graphen und Netzwerke — BFS-Ebenen sind keine kürzesten Wege: die Breitensuche-Demo zeigt, wie stark das bei ungleichen Kosten danebenliegt (Toronto-Netz: im Median 7 %, im schlimmsten Fall 237 % zu lang); die BFS-und-DFS-Demo der Graphen-und-Netzwerke-Linie nennt genau diesen Unterschied als Grenze der Breitensuche (Ebenen zählen Straßen, nicht Kilometer).
- Zustandsschätzung und Filter — Auch Viterbi ist ein kürzester Weg: Die HMM-Dekodieren-Demo der Linie Zustandsschätzung und Filter prüft ihn gegen Dijkstra im Trellis mit den Kosten −log A − log b: Aus einer Folge verrauschter Messungen wird der wahrscheinlichste Weg im Straßennetz.
- Mehrkriterien-Ranking — Die Linie Mehrkriterien-Ranking beginnt dort, wo die Front des Mehrkriterien-Routings schon vorliegt: Die Pareto-Dominanz zeigt an einer gegebenen Menge, wie wenig die Dominanz allein ordnet (bei 20 Alternativen und 5 Kriterien bleiben 71 % unbesiegt), und fragt, wie man aus der Menge eine Rangfolge macht.
- Ordnung und Abhängigkeit — Im kreisfreien Plan genügt ein Durchlauf in topologischer Reihenfolge für kürzeste Wege, auch mit negativen Kosten, wo das Standard-Dijkstra falsch rechnet: Das misst die Wege-und-Hülle-Demo der Linie Ordnung und Abhängigkeit. Dieselbe Idee der Nabenmarken wie das Hub Labeling nutzt die Erreichbarkeit auf großen Plänen dort, aber für die Frage „erreichbar oder nicht“ statt für Distanzen.
- Planarität und Zeichnen — Aus dem Straßennetz-Datensatz der Breitensuche stammt der Auszug von Toronto, den die Separator-Demo der Linie Planarität und Zeichnen auf kleine Trennmengen prüft; die verschachtelte Zerlegung daraus ist auch das Verfahren hinter der Ordnung der Customizable Contraction Hierarchies.
- Netzwerkanalyse — In einer Kontaktfolge zählen nur Kontakte mit wachsenden Zeitmarken: die Demo zu zeitlichen Netzen der Linie Netzwerkanalyse fragt nach Erreichbarkeit statt nach kürzesten Wegen und zeigt, dass zeitrespektierende Wege nicht transitiv sind.
- Netzmodelle — Die Navigierbarkeit fragt, wie gut eine Suche ohne Überblick abschneidet, die nur ihre Nachbarn kennt: Im 60 × 60-Gitter braucht sie mit passenden Fernkontakten im Mittel 14,23 Schritte (bester Exponent etwa 1) gegen 30,6 ohne Fernkontakte; der Dijkstra-Weg bleibt der kürzeste.
Breitensuche im Straßennetz
Sehen Sie, wie die Breitensuche das Netz Schicht für Schicht erkundet und die Route mit den wenigsten Kanten findet: erst alle Nachbarn des Starts, dann deren Nachbarn. Ein Vergleich mit der kostenoptimalen Route zeigt live, wo das genau richtig ist (Labyrinth, Bus-Umstiege: jede Kante kostet dasselbe) und wo nicht: Im Stadtnetz ist ihre Route im Median 23 % länger als die kürzeste.
Demo starten →Dijkstra an Lieferwegen und Straßennetzen
Sehen Sie, wie Dijkstra die Orte nacheinander endgültig festlegt, immer den mit den bisher geringsten Kosten vom Start. Ein Experiment mit negativen Kanten zeigt die Grenze. Der Preis: Dijkstra kennt die Richtung des Ziels nicht und legt bei einem typischen Paar rund die Hälfte des Netzes fest, bevor das Ziel feststeht; schon bei 2 % negativer Kanten liefert er in etwa jedem fünften Zufallsnetz falsche Kosten.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Bidirektionale Suche im Stadt- und Toronto-Netz
Sehen Sie, wie die bidirektionale Suche zusätzlich am Ziel startet und rückwärts läuft: zwei kleine Suchkreise statt eines großen. Ein Umschalter für die Abbruchregel zeigt live, dass schon das erste Treffen beider Suchen nicht sicher die kürzeste Route liefert: Im Stadtnetz ist die Route dann bei 81 % der Paare nicht die kürzeste, und die falsche Regel sieht dabei sogar schneller aus.
Demo starten →Contraction Hierarchies im Toronto-Netz
Sehen Sie, wie Contraction Hierarchies vorab Knoten nach Wichtigkeit zusammenzieht und Abkürzungen einfügt, sodass die Abfrage von beiden Enden nur noch aufwärts sucht. Im echten Toronto-Netz legt sie im Median 21-fach weniger Knoten fest als die bidirektionale Suche. Der Haken: Ändern sich die Kosten, ist die Vorrechnung veraltet, schon bei 2 % veränderten Kanten stimmen bei den meisten Paaren die Kosten nicht mehr.
Demo starten →Bellman-Ford an Frachtnetzen und Devisen
Sehen Sie, wie Bellman-Ford Runde für Runde alle Kanten prüft und dadurch auch negative Kanten (etwa eine Rückvergütung) richtig behandelt, wo Dijkstra Orte zu früh endgültig festlegt. Ein Vergleich mit Dijkstra zeigt live die billigere Route und wie ein Gewinnzyklus gemeldet wird. Der Preis: Ohne negative Kanten braucht das Lehrbuch-Verfahren im Stadtnetz das 1 600-Fache der Arbeit von Dijkstra.
Demo starten →Floyd-Warshall an kleinen und großen Netzen
Sehen Sie, wie Floyd-Warshall die Orte nacheinander als Zwischenstation zulässt und mit drei verschachtelten Schleifen alle kürzesten Wege auf einmal liefert. Ein Umschalter für die Schleifenreihenfolge zeigt, dass nur mit k außen die Matrix stimmt. Der Haken: In dünnen Zufallsnetzen ohne negative Kanten braucht es bei 200 Knoten nach Zählern das 100-Fache von Dijkstra, von jedem Start aus gerechnet.
Demo starten →Johnson an E-Lieferwagen und Zufallsnetzen
Sehen Sie, wie Johnson mit einem einmaligen Bellman-Ford alle Kanten so umgewichtet, dass keine mehr negativ ist und die kürzesten Routen gleich bleiben, sodass danach Dijkstra von jedem Start genügt. Ein Aufwandsvergleich zeigt live, wo sich das lohnt: Beim E-Lieferwagen sind es 22 704 Schritte gegen 262 144 bei Floyd-Warshall, im vollständigen Netz kehrt sich das aber um.
Demo starten →Mehrkriterien-Routing: Zeit gegen CO₂
Sehen Sie, wie das Label-Setting bei zwei Kosten, Fahrzeit und CO₂, statt einer besten Route eine ganze Pareto-Front liefert: alle Routen, die keine andere in beiden Kosten schlägt. Ein Vergleich mit einer gewichteten Summe zeigt live, was sie verpasst: Im Stadtnetz findet sie nur 9 der 29 Routen der Front, und in einer Worst-Case-Kette verdoppelt sich die Front mit jedem Glied.
Demo starten →Zeitabhängiges Routing im Stadtnetz
Sehen Sie, wie das zeitabhängige Dijkstra als Kosten eines Ortes seine Ankunftszeit führt und jede Straße mit der Fahrzeit zu dieser Uhrzeit bewertet. Ein Vergleich mit der Planung nach Tagesmittel zeigt, was feste Kosten kosten: im kleinen Netz um 8:00 39 % mehr Fahrzeit. Der Haken: Das Verfahren stimmt nur, solange späteres Losfahren nie früher ankommen lässt; bei Baustellen kann Warten lohnen, im Stadtnetz aber selten.
Demo starten →Hub Labeling im Stadt- und Zufallsnetz
Sehen Sie, wie beim Hub Labeling jeder Ort vorab eine kurze Liste wichtiger Orte mit Entfernungen bekommt, sodass die Abfrage nur noch zwei sortierte Listen verschmilzt. Im größeren Stadtnetz braucht sie im Mittel 32 Vergleichsschritte statt 210 festgelegter Knoten bei Dijkstra. Der Preis: Speicher, und bei geänderten Kosten sind die Labels veraltet und müssen neu berechnet werden.
Demo starten →Customizable CH bei wechselndem Verkehr
Sehen Sie, wie die Customizable CH Ordnung und Zusammenziehen nur aus der Form des Netzes bildet und die Kosten danach in einer schnellen Phase einträgt. Ein Vergleich mit der alten Contraction Hierarchy zeigt live: Werden 20 % der Straßen dreimal so teuer, liefert die alte für 86 % der Paare eine falsche Entfernung, die angepasste nicht. Der Preis: deutlich mehr Kanten und eine etwas langsamere Abfrage.
Demo starten →RAPTOR an Fahrplänen
Sehen Sie, wie RAPTOR eine Fahrplanauskunft in Runden löst: Runde k findet die früheste Ankunft mit höchstens k Fahrten. Ein Regler für Fußwege und Takt zeigt live, ob es einen Zielkonflikt zwischen früher Ankunft und wenig Umsteigen gibt: Im erfundenen Stadtnetz ohne Fußwege bei nur 3 % der Paare, mit Fußwegen (10 Minuten je Block) bei 95 %.
Demo starten →Welches Verfahren passt zu meiner Routing-Frage?
Zwei Entscheidungsbäume: Baum 1 fragt nach der Art der Frage (gleiche Kosten je Kante, alle Paare, Kosten mit Uhrzeit, zwei Ziele zugleich), Baum 2 führt bei einer einzelnen Route mit festen Kosten zum passenden Verfahren. Alle Antworten stützen sich auf Messungen an den Netzen der Demos.
Baum 1: Welche Art von Routing-Frage?
Baum 2: Eine Route, feste Kosten, welches Verfahren?
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Was die Bäume nicht zeigen: Die Breitensuche liegt bei ungleichen Kosten daneben (im Toronto-Netz im Median 7 %, im schlimmsten Fall 237 % zu lang). Contraction Hierarchies lohnen sich erst in großen, flachen Straßennetzen: Im Toronto-Netz sind es 21-fach weniger festgelegte Knoten als bei der bidirektionalen Suche, im Zufallsnetz nur 0,5-fach, und ändern sich die Kosten, sind sie veraltet. Floyd-Warshall gewinnt nach den Zählern nirgends gegen n-mal Dijkstra, Johnson lohnt im vollständigen Netz nicht. Die statische Planung kostet um 8:00 im Stadtnetz bei Stau-Stärke 1,5 im Mittel 5,9 % Mehrzeit. Beim RAPTOR entsteht der Zielkonflikt erst durch Fußwege (ohne sie bei nur 3 % der Paare).
Weitere Linien in diesem Bereich
Spannbäume
Wie verbindet man alle Standorte mit möglichst wenig Leitung? Elf Stücke vom billigsten Baum über Richtung, Kapazität und Zwischenknoten bis zum Zufallsbaum.
Netzwerkfluss
Wie viel geht durch ein Netz, was kostet es, und was ändert sich, wenn Güter sich Kanten teilen, der Ausbau selbst Entscheidung ist oder die Zeit mitzählt? Neunzehn Stücke von Edmonds-Karp bis zum Fluss über die Zeit.
Schnitte und Zusammenhang
Wie robust hängt ein Netz zusammen, und wie teilt man es in Teile? Acht Stücke über Engstellen, kleinste Schnitte, getrennte Terminals, fehlende Leitungen, ausgewogene Hälften und zusammenhängende Gebiete.
Matching-Algorithmen
Wer wird womit gepaart? 13 Verfahren von der billigsten Kante zuerst bis zum Nierentausch unter medizinischen Zwängen, jedes mit seiner gemessenen Grenze.
Graphen und Netzwerke
Wie durchmustert man ein Netz, welche Kante ist kritisch, wie wichtig ist ein Knoten, und wie verwundbar ist das Ganze? Dreizehn Stücke von BFS/DFS über die interne Verlinkung einer echten Website bis zur eigenen Forschung über Bandbreite.
Härte und Struktur
Welche Sendungen dürfen zusammen fahren? Acht Stücke über Cliquen, Überdeckungen und Baumweite: was Struktur auf einem Konfliktgraphen leicht macht und wo sie nicht reicht.
Ordnung und Abhängigkeit
Ist ein Plan einhaltbar? Neun Stücke über Kreise, kritische Pfade, Ketten und Reihenfolgen: was Abhängigkeiten zwischen Aufgaben bedeuten und wo die Rechnung teuer wird.
Planarität und Zeichnen
Lässt sich ein Netz ohne Überkreuzung zeichnen, und was folgt daraus? Neun Stücke über Färben, Trennen, Zeichnen, Flüsse als kürzeste Wege, Näherung, Zählen und fast planare Netze.
Netzwerkanalyse
Was verrät die Struktur eines Netzes, wie breitet sich etwas darauf aus, und wie gleichen sich seine Betriebe an? Dreizehn Stücke über Kernzahl, Gemeinschaften, Einfluss, Eindämmung, Meinungen, Standorte und Kontaktfolgen.
Netzmodelle
Welches Zufallsmodell erzeugt welche Eigenschaft eines Netzes, wie prüft man ein Netz gegen ein Modell, und was geschieht, wenn keines passt? Neun Stücke vom Zufallsgraphen bis zur Modellwahl.