Command Palette
Search for a command to run...
Einbrechen der Sortierbarriere für gerichtete Einzelquellen-Kürzeste-Wege
Einbrechen der Sortierbarriere für gerichtete Einzelquellen-Kürzeste-Wege
Ran Duan Jiayi Mao Xiao Mao Xinkai Shu Longhui Yin
Abstract
Wir präsentieren einen deterministischen Algorithmus mit Laufzeit O(m log²⁄³ n) für das Problem des kürzesten Pfades von einer Quelle (SSSP) auf gerichteten Graphen mit reellen, nichtnegativen Kantengewichten im Vergleich-Additions-Modell. Dies ist das erste Ergebnis, das die Laufzeitschranke von O(m + n log n) von Dijkstra’s Algorithmus für spärliche Graphen übertrifft und somit zeigt, dass Dijkstra’s Algorithmus für SSSP nicht optimal ist.