Кратчайшие пути — простая задача. Для ориентированного графа с неотрицательными вещественными весами рёбер алгоритм Дейкстры работает за время O(m + n log n), используя фибоначчиеву кучу. При m ≥ n другие детерминированные алгоритмы достигают O(m log^{2/3} n) (прорыв 2025 года) и O(m √log n + √(mn log n log log n)) (продолжение 2026 года).

После примерно 15 часов и 733 сообщений мои агенты предложили новый алгоритм C-HD, проверенный в Lean. Он хорошо справляется с локальным поиском, используя сравнения приоритетов и считая вновь встреченные вершины неисследованными листьями. Он поддерживает локальные инварианты с помощью аккуратного удаления рёбер и ограниченного локального поиска, достигая O(n + m + m log(2 + m/(n+1)) + m^{1/3} (n log(n+2))^{2/3}) в сертифицированном диапазоне m ≤ n⌊⌊log₂ n⌋^{3/4}⌋.

C-HD сокращает повторный поиск и работу со структурами данных, выполняя ограниченные локальные поиски от источника и границы, подсчитывая вновь встреченные вершины и используя деревья поиска и опорные точки для организации рекурсивной работы. Он опирается на отсортированные списки исходящих рёбер. Для небольших или выходящих за диапазон входных данных в начале выбирается отдельный алгоритм Беллмана–Форда со временем работы O((n+1)(m+1)).