418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต II/เฉลยข้อ 4

อัลกอริทึมสำหรับหา cycle ที่สั้นที่สุดที่มี edge $e\,$ เป็นส่วนประกอบ มีดังต่อไปนี้

1. ตัด edge $e\,$ ออกจากกราฟ
2. สมมติว่า $e=\{u,v\}\,$ ให้ทำการหา shortest path จาก $u\,$ ไปยัง $v\,$ ในกราฟที่ตัด $e\,$ ออกไปแล้ว ด้วย Dijkstra's algorithm
3. คืนผลบวกความยาวของ cycle ในข้อ 2 กับ $\ell _{e}\,$ เป็นคำตอบ

เราสามารถแสดงว่าอัลกอริทึมข้างต้นคืนความยาวของ cycle ที่สั้นที่สุดที่มี $e\,$ เป็นส่วนประกอบได้ดังต่อไปนี้

พิจารณา cycle ที่มี $e=\{u,v\}\,$ เป็นส่วนประกอบใดๆ ถ้าเราตัด $e\,$ ออกจาก cycle นั้นเราจะได้ path จาก $u\,$ ไปยัง $v\,$ โดย path นี้ไม่ใช้ $e\,$ ใน cycle ที่มี $e\,$ เป็นส่วนประกอบที่สั้นที่สุดจึงต้องมีความยาวของ path จาก $u\,$ ไปยัง $v\,$ ดังกล่าวที่สั้นที่สุดเท่าที่จะเป็นไปได้ ความยาวที่สั้นที่สุดที่ว่านี้คือความยาวของ shortest path จาก $u\,$ ไปยัง $v\,$ ในกราฟที่ตัด edge $e\,$ ออกไปแล้วนั่นเอง

เราจะเห็นได้ว่าอัลกอริทึมข้างบนมีเวลาการทำงานเท่ากับ Dijkstra's algorithm ซึ่งมีเวลาการทำงานเท่ากับ $O(|V|\log |V|+|E|)=O(|V|^{2})\,$ หากเราใช้โครงสร้างข้อมูล Fibonacci Heap