41 साल बाद नया shortest path algorithm खोजा गया

चीन की Tsinghua University की शोध टीम ने Stanford University के साथ मिलकर पारंपरिक shortest path (single-source shortest path, SSSP) समस्या में computational complexity के लिहाज़ से बड़ी प्रगति हासिल की है। इस शोध को 2025 STOC सम्मेलन में Best Paper पुरस्कार मिला।

पारंपरिक रूप से सबसे अधिक इस्तेमाल किया जाने वाला तरीका Dijkstra algorithm है, जिसकी time complexity O(m + n log n) (n = nodes की संख्या, m = edges की संख्या) के रूप में होती है।
log n पद priority queue या sorting से जुड़े हिस्से से संबंधित है, और पिछले 40 वर्षों में इस हिस्से से आगे निकलने वाला कोई सुधार नहीं हुआ था.

नए algorithm ने time complexity को O(m · log^(2/3) n) तक घटा दिया है।
चूँकि log^(2/3) n, log n की तुलना में अधिक धीमी गति से बढ़ता है, इसलिए nodes की संख्या बहुत बड़ी होने पर यह अंतर काफी बढ़ जाता है.