HyperAIHyperAI

Command Palette

Search for a command to run...

Briser la barrière de tri pour les plus courts chemins à origine unique dirigés

Ran Duan Jiayi Mao Xiao Mao Xinkai Shu Longhui Yin

Abstract

Nous proposons un algorithme déterministe en temps O(mlog2/3n)O(m \log^{2/3} n)O(mlog2/3n) pour le problème des plus courts chemins à source unique (SSSP) sur les graphes orientés munis de poids d'arêtes réels et non négatifs, dans le modèle de comparaison-addition. Il s'agit du premier résultat à briser la borne de temps O(m+nlogn)O(m + n \log n)O(m+nlogn) de l'algorithme de Dijkstra sur les graphes creux, montrant ainsi que l'algorithme de Dijkstra n'est pas optimal pour le problème SSSP.


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

Abonnez-vous à nos dernières mises à jour
Nous vous enverrons les dernières mises à jour de la semaine dans votre boîte de réception à neuf heures chaque lundi matin
Propulsé par MailChimp