Caminhos mais curtos é um problema simples. Dado um grafo direcionado com pesos de arestas reais não negativos, o algoritmo de Dijkstra é executado em tempo O(m + n log n) usando um heap de Fibonacci. Para m ≥ n, outros algoritmos determinísticos alcançam O(m log^{2/3} n) (avanço de 2025) e O(m √log n + √(mn log n log log n)) (continuação de 2026).

Após cerca de 15 horas e 733 mensagens, meus agentes propuseram um novo algoritmo, C-HD, verificado no Lean. Ele lida bem com busca local, usando comparações de prioridade e contando vértices recém-encontrados como folhas inexploradas. Ele mantém invariantes locais com remoção cuidadosa de arestas e busca local limitada, alcançando O(n + m + m log(2 + m/(n+1)) + m^{1/3} (n log(n+2))^{2/3}) dentro do intervalo certificado m ≤ n⌊⌊log₂ n⌋^{3/4}⌋.

C-HD reduz a busca repetida e o trabalho de estruturas de dados executando buscas locais limitadas a partir da fonte e da fronteira, contando vértices recém-encontrados e usando árvores de busca e pivôs para organizar o trabalho recursivo. Ele depende de listas de arestas de saída ordenadas. Para entradas pequenas ou fora do intervalo, um algoritmo Bellman–Ford separado com tempo de execução O((n+1)(m+1)) é selecionado no início.