Ein Forschungsteam der chinesischen Tsinghua University hat in Zusammenarbeit mit der Stanford University einen großen Fortschritt bei der rechnerischen Komplexität des klassischen Problems der kürzesten Wege von einer Quelle aus (single-source shortest path, SSSP) erzielt. Diese Arbeit erhielt auf der STOC 2025 den Best-Paper-Award.
Traditionell wird dafür häufig der Dijkstra-Algorithmus verwendet, dessen Zeitkomplexität die Form O(m + n log n) hat (n = Anzahl der Knoten, m = Anzahl der Kanten).
Der log n-Term hängt mit Priority Queues oder Sortierung zusammen, und in den vergangenen 40 Jahren gab es bei diesem Teil keine Verbesserung, die darüber hinausging.
Der neue Algorithmus senkt die Zeitkomplexität auf O(m · log^(2/3) n).
Da log^(2/3) n langsamer wächst als log n (also weniger stark zunimmt als log n), wird der Unterschied bei sehr großen Knotenzahlen deutlich größer.
18 Kommentare
Das weckt Erinnerungen daran, wie ich Ende der 2000er-Jahre bei einem Anbieter von Fahrzeugnavigationssoftware gearbeitet und ein Modul zur Wegesuche entwickelt habe.
Dijkstra ist für die Routenberechnung in Navigationssystemen viel zu langsam und wird deshalb nicht verwendet; stattdessen nutzt man die heuristisch verbesserte Version, die A*-Suche (A Star). Wie ich nachgesehen habe, ist A* kein SSSP-, sondern ein SPSP-Algorithmus (Single-Pair Shortest Path).
Es wirkt etwas zweifelhaft, zu behaupten, dass er den schnellen Algorithmus für sparse Fälle übertroffen hat.
CLRS wurde doch erst vor nicht allzu langer Zeit überarbeitet – drucken sie jetzt schon wieder neu?
Es fühlt sich an, als wäre nach 41 Jahren ein neues Album von Bands erschienen, die damals aufkamen und bis heute beliebt sind, wie die Beatles oder Oasis. Erst einmal überraschend und spannend, haha.
Vielleicht gab es sie in den USA schon? zitter
Wunderschön, hhh
China legt derzeit wirklich vor.
Ich frage mich, wie der Name des Algorithmus festgelegt wird.
Bald wird jemand unter genau diesen Einschränkungen wohl eine Aufgabe auf Baekjoon erstellen – ich bin schon ganz aufgeregt.
Erinnerungen an Dijkstra..
Wow … das ist der Hammer …
Beeindruckend.
Wow ......
Das klappt tatsächlich ...
Wow~~
Wow....
Dann wird der Stoff in den Algorithmus-Vorlesungen wohl erweitert werden, haha.
Ach du je...