HyperAIHyperAI

Command Palette

Search for a command to run...

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.


Build AI with AI

From idea to launch — accelerate your AI development with free AI co-coding, out-of-the-box environment and best price of GPUs.

AI Co-coding
Ready-to-use GPUs
Best Pricing

HyperAI Newsletters

Abonnieren Sie unsere neuesten Updates
Wir werden die neuesten Updates der Woche in Ihren Posteingang liefern um neun Uhr jeden Montagmorgen
Unterstützt von MailChimp