ทีมนักวิจัยจากมหาวิทยาลัยชิงหวา (Tsinghua University) ร่วมมือกับมหาวิทยาลัยสแตนฟอร์ด สร้างความก้าวหน้าครั้งสำคัญในด้านความซับซ้อนเชิงคำนวณสำหรับปัญหาเส้นทางสั้นที่สุดแบบต้นทางเดียว (single-source shortest path, SSSP) โดยงานวิจัยนี้ได้รับรางวัล Best Paper ในการประชุม STOC 2025
วิธีที่ใช้กันมาอย่างยาวนานคืออัลกอริทึมของ Dijkstra ซึ่งมีความซับซ้อนเชิงเวลาเป็น O(m + n log n) (n = จำนวนโหนด, m = จำนวนเส้นเชื่อม)
พจน์ log n เป็นส่วนที่เกี่ยวข้องกับ priority queue หรือการเรียงลำดับ (sorting) และตลอด 40 ปีที่ผ่านมา ก็ยังไม่มีการปรับปรุงที่ก้าวข้ามข้อจำกัดในส่วนนี้ได้
อัลกอริทึมใหม่นี้ลดความซับซ้อนเชิงเวลาลงเหลือ O(m · log^(2/3) n)
เนื่องจาก log^(2/3) n เพิ่มขึ้นช้ากว่า log n (กล่าวคือเพิ่มขึ้นน้อยกว่า log n) ความแตกต่างจึงยิ่งชัดเจนเมื่อจำนวนโหนดมีขนาดใหญ่มาก
ยังไม่มีความคิดเห็น