Durchbrechung der 40-jährigen Engstelle des Dijkstra-Algorithmus: Professoren aus Tsinghua-Universität et al. überwinden Lehrbuchkonventionen und gewinnen den Besten-Paper-Preis der STOC.

Professor Duan Ran von der Tsinghua-Universität hat eine neue Methode für kürzeste Wege entwickelt, die das klassische Dijkstra-Algorithmus aus den Lehrbüchern geschlagen hat.

Ein bedeutendes Ergebnis in der Informatik!

Ein Professor der Tsinghua-Universität hat das Verständnis des Algorithmus für kürzeste Wege auf den Kopf gestellt und könnte die Informatik-Lehrbücher über Algorithmen neu schreiben.

In der Informatik ist es ein klassisches Problem, den kürzesten Weg von jedem Punkt in einem Netzwerk zu finden. Das Dijkstra-Algorithmus ist die bekannteste Lösung für dieses Problem.

Seit 1956 hat das Problem der kürzesten Wege die Aufmerksamkeit vieler Forscher erregt.

Der Informatiker Mikkel Thorup von der Universität Kopenhagen sagte:

Das Problem der kürzesten Wege ist ein wunderbares Problem, das jeder verstehen kann.

Intuitiv scheint es am einfachsten, den Weg zum nächsten Punkt vom Startpunkt aus zu finden.

Wenn man also einen möglichst schnellen Algorithmus für das Problem der kürzesten Wege entwickeln möchte, ist es sinnvoll, zuerst den nächsten Punkt zu finden, dann den zweitnächsten usw. Dies bedeutet jedoch, dass man ständig feststellen muss, welcher Punkt der nächste ist, d.h., man muss die Punkte nach der Entfernung sortieren.

Allerdings gibt es eine grundlegende Beschränkung bei dieser Methode: Dieser Algorithmus kann nicht schneller sein als die Zeit, die für die Sortierung benötigt wird.

Vor vierzig Jahren stießen Forscher, die an Algorithmen für kürzeste Wege arbeiteten, auf diese "Sortier-Barriere".

Jetzt hat ein Forschungs-Team aus der Tsinghua-Universität und anderen Institutionen einen neuen Algorithmus entwickelt, der diese Barriere überwindet. Dieser Algorithmus hängt nicht von der Sortierung ab und ist schneller als alle Algorithmen, die Sortierung benötigen.

Link zur Publikation: https://arxiv.org/abs/2504.17033

Der Informatiker Robert Tarjan von der Princeton-Universität sagte: "Diese Forscher hatten den Mut zu glauben, dass sie diese Barriere brechen könnten. Dies ist ein erstaunliches Ergebnis."

Es ist erwähnenswert, dass diese Forschung den Besten-Paper-Preis der STOC gewonnen hat, was ihr durchaus gerecht ist.

Links: Mikkel Thorup; Rechts: Robert Tarjan

Kürzeste Wege

Um komplexe Probleme zu lösen, ist es oft hilfreich, sich gut zu organisieren. Beispielsweise kann man das Problem in kleinere Teile zerlegen und zuerst die einfachsten Teile bearbeiten. Doch diese Klassifizierung hat einen Preis: Man kann viel Zeit mit der Sortierung verschwenden.

Dieses Dilemma tritt besonders bei einem der klassischsten Probleme in der Informatik auf: Wie findet man von einem bestimmten Startpunkt aus den kürzesten Weg zu allen anderen Punkten in einem Netzwerk? Dies ist wie das Problem, das man nach einer Umzugslage hat: Man muss die besten Routen von der neuen Wohnung zur Arbeit, zum Fitnessstudio und zum Supermarkt planen.

Um das Problem der kürzesten Wege mathematisch zu analysieren, verwenden Forscher die Sprache der Graphentheorie. Ein Graph ist ein Netzwerk aus Punkten (oder Knoten), die durch Linien verbunden sind. Jede Verbindung hat eine Zahl, die als Gewicht bezeichnet wird und die Länge der Linie oder die Zeit, die man benötigt, um sie zu überqueren, darstellen kann.

Normalerweise gibt es zwischen zwei Knoten viele Wege. Der kürzeste Weg ist derjenige, bei dem die Summe der Gewichte am kleinsten ist. Gegeben einen Graphen und einen bestimmten "Startpunkt", besteht das Ziel des Algorithmus darin, den kürzesten Weg zu jedem anderen Knoten zu finden.

1956 entwickelte der Informatik-Pionier Edsger Dijkstra den später berühmtesten Algorithmus für kürzeste Wege.

Der Algorithmus beginnt am Startpunkt und erweitert sich Schritt für Schritt.

Wie findet das Dijkstra-Algorithmus den kürzesten Weg?

Das Dijkstra-Algorithmus beginnt an einem bestimmten Punkt im Netzwerk und findet den kürzesten Weg zu jedem anderen Punkt. Es findet diese Wege in der Reihenfolge der Entfernung, beginnend mit dem nächsten Punkt.

Die grundlegenden Schritte des Dijkstra-Algorithmus:

Beginne bei Punkt A:

Du siehst zwei Wege. Punkt B ist 1 Einheit entfernt, Punkt C ist 5 Einheiten entfernt. Du weißt jetzt, dass der kürzeste Weg zu B ist, aber es könnte einen kürzeren indirekten Weg zu C geben. Kürzester Weg: A → B = 1

Folge dem kürzesten Weg:

Gehe zu Punkt B und schau erneut um dich. Notiere die Gesamtentfernung von A zu jedem Punkt. Punkt D ist näher an A als Punkt C. Kürzester Weg: A → B = 1; A → D = 2

Setze die Suche fort:

Gehe zu Punkt D und schau erneut um dich. Jetzt hast du den kürzesten Weg zu C gefunden. Kürzester Weg: A → B = 1; A → D = 2; A → C = 3.

Wenn man vom Startpunkt aus beginnt und schrittweise das Netzwerk erkundet, um den kürzesten Weg zu jedem Punkt zu finden, funktioniert diese Methode gut. Denn wenn man den kürzesten Weg zu nahegelegenen Knoten kennt, kann man damit den kürzesten Weg zu weiter entfernten Knoten finden.

Das Endergebnis ist jedoch eine sortierte Liste der kürzesten Wege nach Entfernung. Daher setzt die Sortier-Barriere eine grundlegende Beschränkung für die Geschwindigkeit des Algorithmus.

1984 verbesserten Tarjan und ein anderer Forscher den ursprünglichen Dijkstra-Algorithmus, so dass er diese Geschwindigkeitsgrenze erreichte. Jede weitere Verbesserung muss von einem Algorithmus kommen, der die Sortierung vermeidet.

Link zur Publikation: https://dl.acm.org/doi/10.1145/28869.28874

Anfang der 1990er Jahre und Anfang des 21. Jahrhunderts entwickelten Thorup und andere Forscher Algorithmen, die die Sortier-Barriere überwanden.

Von links nach rechts: Bernhard Haeupler, Václav Rozhoň (oben), Jakub Tětek (unten), Robert Tarjan und Richard Hladík haben bewiesen, dass eine Version des Dijkstra-Algorithmus die beste Lösung für alle Netzwerk-Layouts ist.

Sie mussten bestimmte Annahmen über die Gewichte treffen. Niemand wusste, wie man diese Techniken auf beliebige Gewichte erweitern könnte. Es schien, als hätten sie ein Ende erreicht.

Die Forschung stagnierte lange Zeit, und viele Leute glaubten, dass es keine bessere Lösung gäbe.

Aber Duan Ran von der Tsinghua-Universität gehörte nicht zu diesen Leuten. Er hat lange Zeit geträumt, einen Algorithmus für kürzeste Wege zu entwickeln, der die Sortier-Barriere auf allen Graphen überwindet. Im vergangenen Herbst hat er es endlich geschafft.

Über die Sortierung hinaus

Duan Ran's Interesse an der Sortier-Barriere geht fast 20 Jahre zurück.

Damals war er ein Doktorand an der Universität Michigan. Sein Betreuer war einer der Forscher, die untersuchten, wie man in bestimmten Fällen die Sortier-Barriere überwinden kann.

Aber erst 2021 fand Duan Ran eine vielversprechendere Methode.

Der Schlüssel liegt darin, auf die nächste Richtung in jedem Schritt des Algorithmus zu achten.

Das Dijkstra-Algorithmus nutzt die bereits erkundeten Gebiete, um zu entscheiden, wohin es im nächsten Schritt geht. Dazu scannt es die "Grenze" dieser Gebiete, d.h. alle Knoten, die mit der Grenze verbunden sind. Am Anfang dauert dies nicht viel Zeit, aber mit fortschreitendem Algorithmus wird es langsamer.

Duan Ran hingegen hatte die Idee, benachbarte Knoten an der Grenze in Cluster zu gruppieren. In jedem Schritt wird nur ein Knoten aus jedem Cluster betrachtet. Da es weniger Knoten zu prüfen gibt, kann die Suche in jedem Schritt schneller erfolgen. Der Algorithmus wählt möglicherweise nicht immer den nächsten Knoten, daher ist die Sortier-Barriere nicht mehr anwendbar. Es ist jedoch eine Herausforderung, sicherzustellen, dass diese Cluster-basierte Methode den Algorithmus tatsächlich beschleunigt und nicht verlangsamt.

Im Laufe des folgenden Jahres verfeinerte Duan Ran diese grundlegende Idee.

Im Herbst 2022 war er optimistisch, dass er die technischen Probleme überwinden könnte.

Er holte drei Doktoranden hinzu, um die Details zu verfeinern. Einige Monate später hatten sie teilweise Erfolg: Sie entwickelten einen Algorithmus, der die Sortier-Barriere für beliebige Gewichte überwindet, aber nur für sogenannte ungerichtete Graphen funktioniert.

Link zur Publikation: https://arxiv.org/abs/2307.04139

In ungerichteten Graphen können alle Verbindungen in beide Richtungen benutzt werden. Informatiker interessieren sich normalerweise mehr für die allgemeinere Klasse von Graphen, die gerichtete Wege enthalten. Aber diese "gerichteten Graphen" sind oft schwieriger zu handhaben.

Mao Xiao, ein Doktorand in Informatik an der Stanford-Universität und Mitautor der neuen Publikation, sagte: "In gerichteten Graphen kann es vorkommen, dass es einfach ist, von A nach B zu gelangen, aber schwierig, von B nach A zurückzukehren. Dies kann viele Probleme verursachen."

Der Weg der Hoffnung

Im Sommer 2023 hörte Mao Xiao an einer wissenschaftlichen Konferenz in Kalifornien Duan Ran's Vortrag über den Algorithmus für ungerichtete Graphen. Er sprach sich dann mit diesem seit langem bewunderten Wissenschaftler an. Er war damals sehr aufgeregt, als er Duan Ran zum ersten Mal in der Realität traf.

Wie die Zufälligkeit den Algorithmus optimiert

Nach der Konferenz