418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ II/เฉลยข้อ 6

สมมติให้ $e=(u,v)\,$ เราจะทำการหา simple cycle ที่สั้นที่สุดที่มี edge $e\,$ ได้ด้วยอัลกอริทึมต่อไปนี้

1. ตัด $e\,$ ออกจากกราฟ
2. หา shortest path P จาก $v\,$ ไปยัง $u\,$
3. ตอบ cycle ที่เกิดจากการนำ $(u,v)\,$ เข้าไปรวมกับ $P\,$

เราสามารถหา shortest path ด้วย Dijkstra's algorithm ได้ในเวลา $O((|V|+|E|)\log V)\,$ ฉะนั้นอัลกอริทึมดังกล่าวจึงทำงานในเวลา $O((|V|+|E|)\log V)\,$ ด้วย

เรายังเห็นได้อย่างชัดเจนอีกว่า cycle ที่ตอบก็เป็น cycle ที่สั้นที่สุด เนื่องจาก simple cycle ที่มี edge $(u,v)\,$ จะต้องประกอบด้วย simple path จาก $v\,$ ไป $u\,$ ด้วยเสมอ การใช้ shortest path จาก $v\,$ ไป $u\,$ จึงทำให้เราได้ cycle ที่สั้นที่สุด