शॉर्टेस्ट पाथ एक सरल समस्या है। गैर-ऋणात्मक वास्तविक किनारे भार वाले एक निर्देशित ग्राफ़ को देखते हुए, Dijkstra का एल्गोरिदम Fibonacci हीप का उपयोग करके 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 में सत्यापित किया गया। यह स्थानीय खोज को अच्छी तरह संभालता है, प्राथमिकता तुलनाओं का उपयोग करता है और नए मिले शीर्षों को अन्वेषित पत्तियों के रूप में गिनता है। यह सावधानीपूर्वक किनारे विलोपन और सीमित स्थानीय खोज के साथ स्थानीय अपरिवर्तनीय बनाए रखता है, प्रमाणित सीमा m ≤ n⌊⌊log₂ n⌋^{3/4}⌋ के भीतर O(n + m + m log(2 + m/(n+1)) + m^{1/3} (n log(n+2))^{2/3}) प्राप्त करता है।

C-HD स्रोत और फ्रंटियर से सीमित स्थानीय खोजें चलाकर, नए मिले शीर्षों की गणना करके, और पुनरावर्ती कार्य को व्यवस्थित करने के लिए खोज पेड़ों और पिवोट्स का उपयोग करके बार-बार खोज और डेटा-संरचना कार्य को कम करता है। यह क्रमबद्ध आउटगोइंग-एज सूचियों पर निर्भर करता है। छोटे या सीमा से बाहर के इनपुट के लिए, शुरुआत में O((n+1)(m+1)) रनटाइम वाला एक अलग Bellman–Ford एल्गोरिदम चुना जाता है।