Contraction Hierarchies verständlich erklärt

Um die kürzeste Fahrt durch eine Großstadt zu finden, muss ein Computer nicht jede Kreuzung ansehen, wenn er vorher einmal rechnet. Warum das klappt, was es kostet und wann es nichts bringt, zeigt diese Seite: erst anschaulich, dann für Fachleute.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Von der Seitenstraße zum anderen Stadtrand

Stellen Sie sich vor, Sie wohnen in einer Seitenstraße und wollen zu Freunden am anderen Ende einer großen Stadt. Sie prüfen nicht jede Straße. Sie fahren erst auf eine größere Straße, dann auf eine Hauptachse und am Ziel wieder hinab in die Nebenstraßen. Ihr Kopf kennt eine Rangfolge: Kleine Straßen stehen unten, wichtige oben.

Ein Computer kennt diese Rangfolge zunächst nicht. Er sucht die kürzeste Fahrt, indem er rund um den Start einen wachsenden Kreis von Kreuzungen untersucht. Der Kreis wächst, bis er das Ziel erreicht. Eine Kreuzung ist festgelegt, sobald der Computer den kürzesten Weg dorthin sicher kennt: wie ein Abhaken, nicht wie eine Entscheidung. Die nächste Anfrage beginnt wieder bei null.

Eine bekannte Verbesserung sucht zugleich vom Ziel zurück, bis sich beide Kreise treffen. Doch selbst das legt für ein Beispielpaar aus Start und Ziel in der Innenstadt von Toronto noch 3 547 Kreuzungen fest. Das echte Straßennetz dort hat 10 153 Kreuzungen.

Hier setzt Contraction Hierarchies an. Der Computer baut sich die Rangfolge selbst, einmal vorab. Danach soll jede einzelne Frage weniger Arbeit machen.

Vorab: Kreuzungen zusammenziehen

Zuerst bekommt jede Kreuzung eine Wichtigkeit. Der Computer fragt: Wie viele neue Verbindungen müsste ich einsetzen, wenn ich diese Kreuzung aus dem Plan nehme, verglichen mit den Verbindungen, die dadurch wegfallen? Wer wenig kostet, ist unwichtig und kommt zuerst dran, etwa eine Sackgasse: Nimmt man sie heraus, ist nichts zu ersetzen. Das Herausnehmen heißt zusammenziehen.

Nehmen wir an, die Kreuzung X liegt zwischen den Kreuzungen A und B. Von A nach X sind es drei Minuten, von X nach B zwei. Nimmt man X heraus, ginge der Weg über X verloren. Deshalb setzt der Computer eine direkte Verbindung von A nach B ein, fünf Minuten lang. Sie heißt Abkürzung. So bleiben alle Entfernungen zwischen den übrigen Kreuzungen gleich.

Manchmal braucht es die Abkürzung nicht. Führt schon ein anderer Weg von A nach B, der höchstens so lang ist, spart man sie sich. Eine Nebenstraße von A nach B in vier Minuten macht die fünf Minuten über X überflüssig. Dieser andere Weg heißt Zeuge, denn er bezeugt: Hier geht nichts verloren.

So zieht der Computer Kreuzung für Kreuzung zusammen, von der unwichtigsten zur wichtigsten. Jede bekommt einen Rang. Am Ende liegt das ursprüngliche Straßennetz samt aller eingesetzten Abkürzungen im Speicher. Dieses Vorrechnen läuft nur einmal. Im Toronto-Beispiel kamen dabei sehr viele Abkürzungen hinzu, mehr als es ursprüngliche Straßenstücke gibt. Die Rechnung dauerte einige Sekunden.

Die Frage: erst hinauf, dann hinab

Kommt nun eine Frage, sucht der Computer vom Start und vom Ziel gleichzeitig, aber nur nach oben: nur zu Kreuzungen mit höherem Rang. Beide Suchen steigen, bis sie sich treffen. Das genügt, weil es zu jeder kürzesten Fahrt eine gleich lange gibt, die in der Rangfolge zuerst steigt und dann fällt: Wo sie in einem Tal verliefe, ersetzt eine Abkürzung oder ein Zeuge das Stück. Die Fahrt hat also die Form eines Berges. Zum Schluss ersetzt der Computer jede Abkürzung wieder durch die Straßenstücke, die sie vertritt.

Im Toronto-Beispielpaar legt diese Suche nur 176 Kreuzungen fest. Bei 30 zufällig gewählten Paaren sind es beim mittleren Ergebnis (dem Median) etwa 21 Mal weniger als bei der Suche von beiden Enden. Auf jedem geprüften Paar stimmte die Fahrzeit mit der einfachen Suche überein. Das ist gemessen, nicht für alle Paare bewiesen. Ein Grund: Abkürzungen bilden nur Wege ab, die es ohnehin gibt.

Wann die Rangfolge nichts bringt

Eine Rangfolge hilft nur, wenn das Netz eine hat. Im Straßennetz laufen viele Wege über wenige Hauptstraßen: Das ist die übliche Erklärung. Die Ursachen unten sind Deutungen, gemessen sind nur die Ergebnisse. Vier Netze im Vergleich, jeweils gegenüber der Suche von beiden Enden (der oben genannten Verbesserung):

• Echtes Straßennetz (Toronto Innenstadt): etwa 21 Mal weniger festgelegte Kreuzungen. Mögliche Ursache: Wenige Hauptstraßen tragen viele Wege.
• Erzeugtes Gitternetz (Stadtplan aus gleichartigen Straßen): nur wenig besser, im Mittel über fünf erzeugte Netze der Beispielgröße. Mögliche Ursache: Keine Straße ist wichtiger als die anderen, also gibt es kaum eine Rangfolge.
• Erzeugtes Zufallsnetz (Orte mit zufälligen Verbindungen): schlechter, die schnelle Suche legt mehr Kreuzungen fest. Mögliche Ursache: Zufällige Querverbindungen führen von jeder Kreuzung in wenigen Schritten fast überallhin, also gibt es keine Hauptwege.
• Kleines Netz mit acht Orten: schlechter, die schnelle Suche legt acht Orte fest, die Suche von beiden Enden nur sieben. Mögliche Ursache: Bei acht Orten gibt es nichts zu sparen, nur Aufwand.

Vorrechnen lohnt sich also nur, wenn viele Fragen an ein Netz mit Hauptwegen kommen: Es kostet einmal Zeit und Platz im Speicher, und jede Frage spart davon nur ein Stück zurück.

Wenn sich die Straßen ändern

Die Abkürzungen tragen die Fahrzeiten vom Tag der Vorberechnung in sich. Wird eine Straße später langsamer, etwa durch eine Baustelle, weiß die Rangfolge nichts davon. Sie meldet weiter die alte Zeit, ohne Warnung.

Das wurde in Toronto ausprobiert. Bei 2 % der Straßenstücke, zufällig gewählt, wurde die Fahrzeit verdoppelt. Danach stimmte bei einer Auswahl zufälliger Paare die gemeldete Fahrzeit für 78 % der Paare nicht mehr. Bei 60 % war die gefundene Fahrt außerdem nicht mehr die kürzeste. Die beiden Werte sind verschieden, weil eine Fahrt die beste bleiben kann, während ihre gemeldete Zeit trotzdem veraltet ist.

Neu vorrechnen (geprüft bei einem etwas größeren Anteil geänderter Straßenstücke) behebt das: Danach stimmten alle Paare dieser Auswahl wieder. Das Neurechnen kostet aber jedes Mal Zeit, im Toronto-Beispiel einige Sekunden.

Häufige Missverständnisse

• „Der Computer muss wissen, welche Straße eine Hauptstraße ist.“ Nein. Er probiert aus, wie viele Abkürzungen das Herausnehmen einer Kreuzung kostet. Die Rangfolge entsteht aus der Form des Netzes, nicht aus Straßenklassen.
• „Weniger Abkürzungen heißt bessere Rangfolge.“ Nicht unbedingt. Man könnte Kreuzungen auch nur nach der Zahl ihrer Nachbarn ordnen. Im Gitternetz entstanden damit weniger Abkürzungen, doch die Fragen legten danach mehr Kreuzungen fest.

Woran Sie das im Alltag erkennen

• Sie planen eine lange Fahrt in Stufen: erst zur nächsten Hauptstraße, dann auf der Hauptachse, am Ende wieder hinab.
• Sie haben sich eine Route notiert, doch eine Straße ist inzwischen gesperrt. Die Notiz sieht unverändert richtig aus, und Sie merken den Fehler erst unterwegs. So veraltet auch eine vorgerechnete Rangfolge.

Wie ernst sind die Zahlen zu nehmen?

Die Zahlen zählen festgelegte Kreuzungen, nicht Sekunden: Sie zeigen den Arbeitsaufwand einer Frage, nicht die Geschwindigkeit eines Navigationsgeräts. Toronto ist ein einziger Ausschnitt echter Straßendaten, die anderen Netze sind erzeugt.

Was Sie mitnehmen

• Fragen Sie bei jeder schnellen Antwort, was vorher berechnet wurde.
• Fragen Sie, ob sich die Grundlage seitdem geändert hat. Eine vorgerechnete Antwort warnt nicht, wenn sie veraltet ist.
• Fragen Sie, ob das Netz Hauptwege hat. Ohne sie bringt Vorrechnen wenig.

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser, die Demo. Sie erreichen es über den ersten Knopf unten. Zum Verstehen brauchen Sie es nicht. Der zweite Knopf führt zum zweiten Teil für Fachleute.

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.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Gegeben ist ein gerichteter Graph \(G=(V,E)\) mit Knotenzahl \(n=|V|\) und Kantenkosten \(c_e \ge 0\), in der Demo ganze Zahlen. Gesucht sind kürzeste Wege für viele Start-Ziel-Paare \((s,t)\) im selben Netz. Contraction Hierarchies (CH) trennen die Arbeit in eine Vorberechnung, einmal je Netz, und eine Abfrage je Paar. Die Vorberechnung bestimmt eine Ordnung \(r: V \to \{1,\dots,n\}\), den Rang jedes Knotens, zieht die Knoten in dieser Reihenfolge zusammen und fügt dabei Abkürzungen ein.

• Kleines Netz: acht Orte in zwei Ortsgruppen, verbunden durch eine schnelle Verbindung, mit fester Aufgabe (ein Start, ein Ziel); Kosten in Fahrminuten.
• Stadtnetz (erzeugt): gestörtes Raster, Kreuzungen mit Lageabweichung, verbunden mit allen Nachbarn bis zu einer Reichweite in Blocklängen. Kosten einer Straße: Länge mal \((1 + \text{Streuung} \cdot U)\) mit \(U\) gleichverteilt zwischen null (eingeschlossen) und eins (ausgeschlossen), unabhängig je Straße, auf ganze Meter gerundet (mindestens 1). Verbunden werden nur Nachbarn, zwischen denen die Verbindung keinen weiteren Knoten überspringt. Ein Anteil der Straßen ist gesperrt, die Kante fällt dann in beiden Richtungen weg; das Netz bleibt zusammenhängend. Voreinstellung: 20 × 20 Kreuzungen, Reichweite 2.3, Streuung 1, 20 % gesperrt.
• Zufallsnetz (erzeugt): zusammenhängender Zufallsgraph; jeder Knoten hängt an einem früheren, dann kommen zufällige Kanten bis zum mittleren Grad (Voreinstellung 4, wählbar von 2.5 bis 6). Ganzzahlige Kosten von 1 bis 9. Die Kugeln um einen Knoten wachsen hier mit der Zahl der Schritte exponentiell.
• Toronto Innenstadt: befahrbares Netz im 9-km-Umkreis der City Hall aus OpenStreetMap-Daten, 10 153 Knoten, 26 985 gerichtete Kanten (Einbahnstraßen sind gerichtete Kanten), Kosten in ganzen Metern.
• Aufwandsmaß: die Zahl der Knoten, die eine Suche bis zum Ziel festlegt (deren Entfernung sie endgültig kennt). Verglichen werden einseitiges Dijkstra, die bidirektionale Suche und die CH-Abfrage. Das Auspacken der Route zählt nicht mit. Laufzeiten sind rechnerabhängige Messwerte in reinem Python.
• Gewinn: je Paar die Zahl der von der bidirektionalen Suche festgelegten Knoten geteilt durch die der CH-Abfrage; ausgewiesen wird der Median dieses Verhältnisses über die Paare. Das Verhältnis der Mediane der Knotenzahlen fiele für Toronto etwas höher aus (Rechnung dieser Seite).

Die Verfahren und Formeln

Zusammenziehen. Der Restgraph vor dem \(i\)-ten Schritt sei \(G_i\). Beim Zusammenziehen von \(v\) wird für jedes Paar \(u \to v \to w\) mit \(u \ne w\) geprüft, ob in \(G_i \setminus \{v\}\) ein Weg \(u \leadsto w\) mit Kosten \(\le c(u,v)+c(v,w)\) existiert; ein solcher Weg heißt Zeuge. Gibt es keinen, kommt die Kante \((u,w)\) mit den Kosten \(c(u,v)+c(v,w)\) und dem Mittelknoten \(v\) hinzu, eine Abkürzung. \(G_{i+1}\) ist \(G_i \setminus \{v\}\) plus diese Abkürzungen. Gibt es mehrere Wege zum selben Paar, bleibt die billigste Kante. Grade zählen verschiedene Nachbarn im Restgraphen.

Zeugensuche. Je Eingangsnachbar \(u\) läuft ein begrenztes Dijkstra in \(G_i \setminus \{v\}\), das alle Ausgangsnachbarn \(w\) bedient. Es bricht ab, wenn sein kleinster Schlüssel über \(c(u,v)\) plus der größten Ausgangskante von \(v\) liegt oder wenn es die Zeugengrenze erreicht hat, eine Höchstzahl festgelegter Knoten (wählbar 1, 5, 20 oder 200, Voreinstellung 200). Bricht die Suche vor einem möglichen Zeugen ab, entsteht eine überflüssige Abkürzung; die Invariante unten bleibt erhalten.

Wichtigkeit. Die Voreinstellung ordnet nach der Wichtigkeit \(ED(v) + N_c(v)\). Dabei ist \(N_c(v)\) die Zahl der schon zusammengezogenen Nachbarn von \(v\) und \(ED(v)\) die Kantendifferenz im Restgraphen \(G_i\):

\[ED(v)=\#\text{Abkürzungen}(v)-\bigl(\deg_{\text{ein}}(v)+\deg_{\text{aus}}(v)\bigr)\]

Wer die kleinste Wichtigkeit hat, kommt zuerst dran; bei Gleichstand entscheidet die kleinere Knotennummer. Die Zahl der Abkürzungen wird in einem Probelauf geschätzt, dessen Zeugengrenze höchstens so groß ist wie die des eigentlichen Zusammenziehens (bei den Zeugengrenzen 20 und 200 kleiner, bei 1 und 5 gleich). Vier Ordnungen sind wählbar: Kantendifferenz „träge neu geprüft“ (Voreinstellung; die Wichtigkeit wird einmal am Anfang berechnet und beim Entnehmen neu geprüft, zusammengezogen wird nur, wenn sie nicht schlechter ist als die des nächsten Knotens), Kantendifferenz „Nachbarn neu bewertet“ (nach jedem Schritt für die Nachbarn neu), „nur Grad“ (Grad im Restgraphen) und „zufällig“ (nur für kleine Netze zur Wahl).

Hierarchie und Abfrage. \(G^{+}\) enthält alle Kanten von \(G\) und alle Abkürzungen. \(G^{\uparrow}\) besteht aus den Kanten \((u,v)\) mit \(r(u) < r(v)\), \(G^{\downarrow}\) aus denen mit \(r(u) > r(v)\). Die Abfrage sucht vorwärts ab \(s\) auf \(G^{\uparrow}\) und rückwärts ab \(t\) auf den umgedrehten Kanten von \(G^{\downarrow}\), also von \(t\) aus ebenfalls aufwärts. Sei \(d_f(x)\) die beste bisher gefundene Entfernung von \(s\) zu \(x\) auf \(G^{\uparrow}\) und \(d_b(x)\) die von \(t\) zu \(x\) auf den umgedrehten Kanten von \(G^{\downarrow}\). Beide Seiten halten ihre Knoten in einer Prioritätswarteschlange; der Schlüssel eines Knotens ist seine vorläufige Entfernung. Sei \(\mu\) die kleinste Summe \(d_f(x)+d_b(x)\) über Knoten \(x\), die beide Seiten schon erreicht haben (anfangs unendlich). Jede Seite endet, wenn ihre Warteschlange leer ist oder ihr kleinster Schlüssel \(\mu\) erreicht. Der Treffknoten ist der Knoten höchsten Rangs der Route; zum Schluss wird jede Abkürzung durch ihren Mittelknoten ersetzt, bis nur Originalkanten übrig sind.

Richtigkeit Schritt für Schritt

Die folgende Herleitung ist eine Beweisskizze dieser Seite nach der Argumentation der Demo, nicht formal ausgeführt. Sie setzt \(c_e \ge 0\) voraus.

• Schritt 1, Invariante: Beim Zusammenziehen von \(v\) bleiben die Entfernungen zwischen allen verbleibenden Knoten gleich. Ein Weg in \(G_i\) über \(u \to v \to w\) hat in \(G_{i+1}\) entweder die Abkürzung \((u,w)\) mit gleichen Kosten oder einen Zeugen, der nicht länger ist. Wege, die \(v\) nicht berühren, bleiben unverändert.
• Schritt 2, Abbruch der Zeugensuche: Jede Abkürzung entspricht einem wirklichen Weg in \(G\). Eine überflüssige Abkürzung kann deshalb keine Entfernung verkleinern. Gebraucht werden Zeugen nur, um Abkürzungen zu sparen, nicht für die Richtigkeit. Mehr Abkürzungen kosten allerdings auch Abfrageaufwand (siehe Befunde).
• Schritt 3, die Bergroute: \(P\) sei eine kürzeste Route von \(s\) nach \(t\). Liegt auf \(P\) ein Knoten \(y\) mit niedrigerem Rang als beide Nachbarn \(u, w\) auf \(P\), wurde \(y\) vor \(u\) und \(w\) zusammengezogen. Nach Schritt 1 lässt sich \(u \to y \to w\) durch die Abkürzung oder einen Zeugen ersetzen, ohne \(P\) zu verlängern. Wiederholtes Ersetzen liefert eine Route gleicher Länge ohne inneres Rangminimum. Das Ersetzen endet: Bei jedem Ersatz entfällt \(y\), und alle neu hinzukommenden Knoten haben höheren Rang als \(y\), denn sie lagen noch im Restgraphen, als \(y\) zusammengezogen wurde. Die Rangliste der Routenknoten wächst damit lexikographisch von unten, und davon gibt es nur endlich viele. Schleifen, die ein Zeuge einführt, lassen sich wegen \(c_e \ge 0\) ohne Kostenverlust abschneiden. Eine Route ohne inneres Rangminimum steigt erst und fällt dann. Ihre Spitze \(x\) ist der Knoten höchsten Rangs der Endroute, nicht notwendig der ursprüngliche.
• Schritt 4, die Abfrage findet sie: Mit \(x\) als Spitze der Endroute liegt der Teil \(s \leadsto x\) in \(G^{\uparrow}\), der Teil \(x \leadsto t\), rückwärts gelesen, ebenfalls. Kürzer als diese Route kann nichts sein, denn jede Route in \(G^{+}\) ergibt nach dem Auspacken eine Route in \(G\).
• Schritt 5, Abbruch der Abfrage: Erreicht der kleinste Schlüssel einer Seite \(\mu\), kann kein Knoten dahinter eine Route unter \(\mu\) vervollständigen, weil alle Kosten nichtnegativ sind. Die Seite darf enden.

Durchgerechnetes Beispiel einer Zusammenziehung

Rechnung dieser Seite, keine Messung: Der Knoten \(v\) liegt zwischen \(u\) und \(w\), mit \(c(u,v)=3\) und \(c(v,w)=2\). Der Weg über \(v\) kostet 5. Ob eine Abkürzung entsteht, hängt davon ab, was die Zeugensuche in \(G_i \setminus \{v\}\) findet:

Fall	Bester Weg \(u \leadsto w\) ohne \(v\)	Vergleich mit 5	Folge
Nebenstraße	4	4 ≤ 5	Zeuge, keine Abkürzung
Gleichstand	5	5 ≤ 5	Zeuge, keine Abkürzung
Umweg	6	6 > 5	Abkürzung \((u,w)\) mit Kosten 5, Mittelknoten \(v\)
kein Weg gefunden	unbekannt	nicht prüfbar	Abkürzung mit Kosten 5, vielleicht überflüssig

Das Beispiel zeigt auch, warum ein Abbruch der Zeugensuche (letzte Zeile) die Richtigkeit nicht gefährdet: Die eingefügte Kante bildet einen echten Weg der Länge 5 ab. Er kostet aber Platz und Aufwand (siehe Befunde). Eine Nachrechnung dieser Seite am kleinen Netz (keine Messung der Demo) ergibt für das feste Paar eine Route aus drei Originalkanten, bei der die Abfrage keine Abkürzung benutzt.

Befunde

Maßstab ist die Zahl der festgelegten Knoten. Der Netzvergleich nimmt 30 zufällige erreichbare Paare je Netz und bildet den Median des Gewinns; beim Stadtnetz und beim Zufallsnetz wird über fünf erzeugte Netze gemittelt, Toronto ist ein einziges Netz. Die Regler-Reihen am Stadtnetz und am Zufallsnetz stehen unter derselben Mittelung über fünf Netze. Das Stadtnetz hat die Voreinstellung (20 × 20), außer wo die Größe selbst variiert wird.

Frage	Befund
Lohnt sich CH im kleinen Netz?	Nein. Beim Zusammenziehen entstehen 6 gerichtete Abkürzungen (drei Paare), an mehreren Stellen genügt ein Umweg als Zeuge. Die CH-Abfrage legt 8 Knoten fest, die bidirektionale Suche 7.
Was bringt CH im Straßennetz (Toronto Innenstadt)?	Median des Gewinns gegenüber der bidirektionalen Suche: 21-fach (30 Paare). Für das gezeigte Paar legen CH-Abfrage, bidirektionale Suche und einseitiges Dijkstra 176, 3 547 und 6 093 Knoten fest. Die Vorberechnung fügt 37 340 Abkürzungen ein (1.4 je Kante) und dauerte einige Sekunden (laut Dokumentation etwa 3 Sekunden, bei einer Nachprüfung auf anderem Rechner mehr; nicht getestet, rechnerabhängig).
Was bringt CH im Stadtnetz (Gitter)?	Median des Gewinns im Mittel über fünf Netze nur 1.1-fach. Für das gezeigte Paar 51 Knoten gegen 126 (bidirektional) und 241 (Dijkstra). Reichweite 1.0 / 1.5 / 2.3 / 3.2: 3.3- / 1.9- / 1.1- / 0.9-fach (mehr Kanten je Kreuzung senken den Gewinn; Deutung der Demo: dichte Netze verlieren ihre Hierarchie). Größe 10 / 20 / 30 Kreuzungen je Seite: 0.8- / 1.1- / 1.4-fach.
Was bringt CH im Zufallsnetz?	0.5-fach: Im Median legt die CH-Abfrage mehr Knoten fest als die bidirektionale Suche, und die Vorberechnung fügt 1.9 Abkürzungen je Kante ein. Mittlerer Grad 2.5 / 4 / 6: 1.2- / 0.6- / 0.4-fach.
Wie wirkt die Ordnung? (Stadtnetz 16 × 16, fünf Netze)	Zufällige Ordnung 2.0 Abkürzungen je Kante, Kantendifferenz 0.6 bis 0.7. „Nur Grad“ braucht mit 0.4 sogar weniger, aber die Abfrage legt mehr Knoten fest. In Toronto lief die zufällige Ordnung in einem einzigen Versuch nach 280 Sekunden nicht durch (einmalige Messung).
Wie wirkt die Zeugengrenze? (Toronto, 30 Paare)	Bei 1 / 5 / 20 / 200 Knoten je Zeugensuche 3.1 / 2.2 / 1.5 / 1.4 Abkürzungen je Kante, in allen Fällen ohne falsche Kosten. Nachprüfung dieser Seite, keine Messung der Demo: Die Kantenprüfungen je Abfrage lagen bei Grenze 1 rund sechsmal so hoch wie bei Grenze 200; weniger Zeugen kosten also nicht nur Platz.
Was geschieht bei geänderten Kosten? (Toronto, 40 Paare, Kosten einzelner Kanten verdoppelt)	Schon bei 2 % verdoppelten Kanten stimmen bei etwa 78 % der Paare die berichteten Kosten nicht mehr, und bei 60 % ist die Route nicht mehr die kürzeste (im Mittel 2 % zu lang). Bei 20 % sind es 100 % und 95 %. Neu vorrechnen (bei 5 % geänderten Kanten geprüft, einige Sekunden) macht alle 40 Paare wieder exakt.
Ist die Abfrage richtig?	Auf jedem geprüften Paar (alle Netze, alle Ordnungen, alle Zeugengrenzen) liefert die CH-Abfrage die Kosten von einseitigem Dijkstra und von networkx.

Grenzen und was die Messung zeigt

• Was sie belegt: die Richtung der Effekte (Hierarchie im Straßennetz, keine im Zufallsnetz, kleiner Vorteil im Gitter) und die Größenordnung der Gewinne auf diesen Netzen. Die Richtigkeit der Abfrage ist an allen geprüften Paaren bestätigt, nicht allgemein bewiesen; die Beweisskizze oben stützt sie.
• Ein Netz, eine Paarauswahl: Der Gewinn für Toronto hängt von der Auswahl der Paare ab. Nachrechnung dieser Seite, keine Messung der Demo: Bei mehreren unabhängigen Ziehungen schwankte der Median von rund einem Dutzend bis über zwanzig (30 Paare je Ziehung) und, enger, zwischen etwa dreizehn und achtzehn (100 Paare je Ziehung); der Mittelwert der 100-Paar-Ziehungen lag etwa ein Viertel unter dem ausgewiesenen Wert. Der ausgewiesene Wert liegt am oberen Rand dieser Spanne. Die Größenordnung (mehr als das Zehnfache) bleibt, schon die Zehnerstelle gilt nicht.
• Zufallsnetz: Die Werte 0.5-fach (30 Paare) und 0.6-fach bei Grad 4 (weniger Paare) beschreiben dasselbe Netz und liegen innerhalb der Prüftoleranz; beide bedeuten „schlechter als bidirektional“.
• Aufwandsmaß statt Laufzeit: Gemessen werden festgelegte Knoten. Laufzeiten sind Einzelmessungen eines Rechners in reinem Python; der Punkt, ab dem sich das Vorrechnen gegenüber Dijkstra ausgleicht, ist ein Messwert dieses Rechners und wird weder behauptet noch geprüft.
• Hierarchie und Straßennetz: Dass Straßennetze eine Hierarchie haben, weil viele Wege über wenige Hauptstraßen laufen, ist die übliche Erklärung. Hier ist sie nur durch die Netzvergleiche gestützt, nicht getrennt geprüft.
• Geänderte Kosten: Geprüft sind nur Verdopplungen zufällig gewählter Kanten in einem Netz; bei nur 40 Paaren liegen 95 % und 100 % innerhalb der Stichprobenstreuung. Reale Staus sind nicht zufällig verteilt. Die „2 % zu lang“ beziehen sich nach der Berechnung der Demo auf die Paare, deren Route nicht mehr die kürzeste ist, nicht auf alle Paare. Das Neuvorrechnen wurde bei 5 % geänderten Kanten geprüft.
• Ordnung und Zeugengrenze: Verglichen werden vier Ordnungsregeln; ob es bessere gibt, ist nicht untersucht. Die zufällige Ordnung gibt es in großen Netzen nicht zur Wahl, ihr Versuch in Toronto ist einmalig.
• Modellgrenzen: nichtnegative feste Kosten, nur Start-Ziel-Anfragen (für alle Paare auf einmal gibt es andere Verfahren), keine Abbiegekosten und keine zeitabhängigen Kosten. Der Speicher für die Abkürzungen wächst mit dem Netz: in Toronto 1.4 Abkürzungen je Kante.

Erweiterungen und Verweise

Nicht Teil dieser Demo sind angepasste Hierarchien für wechselnde Kosten und Verfahren, die die Suche ganz vorwegnehmen. Verwandte Seiten und Demos:

• Einseitige Suche: Die Seite zum Dijkstra-Algorithmus erklärt die Suche im wachsenden Kreis.
• Suche von beiden Enden: Die bidirektionale Demo zeigt das Vergleichsverfahren dieser Seite.
• Wechselnde Kosten: Die Demo zu Customizable CH bildet Ordnung und Zusammenziehen nur aus der Form des Netzes und trägt die Kosten danach ein; sie vergleicht live mit der alten Hierarchie.

Quellen

• Geisberger, R., Sanders, P., Schultes, D., Delling, D. (2008): Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. Workshop on Experimental Algorithms.
• Khamis, A.: Optimization Algorithms, Kapitel 4.3.4 (nur die Idee ist übernommen).
• Kartendaten © OpenStreetMap-Mitwirkende, Open Database License (ODbL) 1.0.
• Quelltext, Messreihe und Tests der Demo: github.com/sebastian-hanisch/contraction-hierarchies-demo.

Die Arbeit von Geisberger u. a. (2008) und das Buchkapitel sind in der Dokumentation der Demo genannt; Titel und Tagung der Arbeit sind aus dem Gedächtnis, nicht im Original geprüft. Die Beweisskizze, das Zahlenbeispiel und die Nachrechnung zur Paarauswahl sind Rechnungen dieser Seite und keine Messungen.