Apresentamos um algoritmo determinístico de O (m^2/3n) para caminhos mais curtos de fonte única (SSSP) em grafos direcionados com pesos de arestas reais não negativos no modelo de comparação-adição. Este é o primeiro resultado a quebrar o limite de tempo O (m+n n) do algoritmo de Dijkstra em grafos esparsos, mostrando que o algoritmo de Dijkstra não é ótimo para SSSP.
Duan et al. (qua,) estudaram essa questão.