Jalur terpendek adalah masalah sederhana. Diberikan graf berarah dengan bobot sisi real non-negatif, algoritma Dijkstra berjalan dalam waktu O(m + n log n) menggunakan Fibonacci heap. Untuk m ≥ n, algoritma deterministik lain mencapai O(m log^{2/3} n) (terobosan 2025) dan O(m √log n + √(mn log n log log n)) (tindak lanjut 2026).

Setelah sekitar 15 jam dan 733 pesan, agen saya mengusulkan algoritma baru, C-HD, yang diverifikasi di Lean. Algoritma ini menangani pencarian lokal dengan baik, menggunakan perbandingan prioritas dan menghitung simpul yang baru ditemui sebagai daun yang belum dijelajahi. Algoritma ini mempertahankan invarian lokal dengan penghapusan sisi yang hati-hati dan pencarian lokal terbatas, mencapai O(n + m + m log(2 + m/(n+1)) + m^{1/3} (n log(n+2))^{2/3}) dalam rentang tersertifikasi m ≤ n⌊⌊log₂ n⌋^{3/4}⌋.

C-HD mengurangi pencarian berulang dan pekerjaan struktur data dengan menjalankan pencarian lokal terbatas dari sumber dan perbatasan, menghitung simpul yang baru ditemui, dan menggunakan pohon pencarian dan pivot untuk mengatur pekerjaan rekursif. Algoritma ini bergantung pada daftar sisi keluar yang terurut. Untuk masukan kecil atau di luar rentang, algoritma Bellman–Ford terpisah dengan waktu jalan O((n+1)(m+1)) dipilih di awal.