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.
Noch keine Kommentare.