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

อัลกอริทึมในการหา cycle ที่สั้นที่สุดมีดังต่อไปนี้

1. รัน Floyd's algorithm บนกราฟ $G\,$ และสมมติให้ output ของมันอยู่ในอะเรย์ $M[\cdot ,\cdot ]\,$
2. สำหรับ edge $(u,v)\,$ แต่ละ edge ใน $G\,$ ให้คำนวณค่า $M[v,u]+\ell _{(u,v)}\,$ โดยที่ $\ell _{(u,v)}\,$ คือความยาวของ edge $(u,v)\,$ แล้วจำค่า $M[v,u]+\ell _{(u,v)}\,$ ที่ต่ำสุดเอาไว้
3. ถ้าค่าที่ต่ำที่สุดในข้อ 2 เป็น $\infty \,$ ก็ให้ตอบว่าไม่มี cycle มิเช่นนั้นให้คืนมันเป็นคำตอบ

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

กรณีที่ 1: ถ้ากราฟไม่มี cycle เราจะได้ว่าสำหรับทุกๆ edge $(u,v)\,$ จะไม่มี path จาก $v\,$ ไปยัง $u\,$ ดังนั้น $M[v,u]=\infty \,$ เสมอ ด้วยเหตุนี้ค่า $M[v,u]+\ell _{(u,v)}\,$ ที่ต่ำที่สุดจึงมีค่าเท่ากับ $\infty \,$ และอัลกอริทึมข้างบนจะตอบว่ากราฟไม่มี cycle ได้อย่างถูกต้อง

กรณีที่ 2 ถ้ากราฟมี cycle เราจะได้ว่ามี edge $(u,v)\,$ อย่างน้อยหนึ่ง edge ที่ทำให้ $M[u,v]+\ell _{(u,v)}\,$ มีค่าน้อยกว่า $\infty \,$ เราจะต้องแสดงว่าค่า $M[v,u]+\ell _{(u,v)}\,$ ที่น้อยที่สุดคือความยาวของ cycle ที่สั้นที่สุด

อันดับแรก ให้พิจารณา edge $(u,v)\,$ ใดๆ เราได้ว่า $M[v,u]\,$ คือความยาวของ shortest path จาก $v\,$ ไปยัง $u\,$ ด้วยเหตุนี้ $M[v,u]+\ell _{(u,v)}\,$ จึงเป็นความยาวของ cycle ที่สั้นที่สุดที่มี edge $(u,v)\,$ (เราสามารถแสดงว่าข้อความสุดท้ายนี้เป็นจริงได้โดยการสมมติให้เกิดข้อขัดแย้งว่า $M[v,u]+\ell _{(u,v)}\,$ ไม่ใช่ความยาวของ cycle ที่สั้นที่สุดที่มี edge $(u,v)\,$ แต่เราจะได้ว่า cycle นั้นจะต้องมี path จาก $v\,$ ไปยัง $u\,$ และไม่มี path จาก v ไป u ที่มีความยาวน้อยกว่า $M[v,u]\,$ แล้ว ทำให้เกิดข้อขัดแย้งขึ้น)

อันดับที่สอง เนื่องจาก cycle ที่สั้นที่สุดจะต้องผ่าน edge อย่างน้อย 1 edge เราจึงได้ว่าการนำความยาว cycle ที่สั้นที่สุดที่ผ่าน edge แต่ละ edge มาเปรียบเทียบกัน เพื่อหาความยาวที่น้อยที่สุดจะทำให้เราได้ความยาวของ cycle ที่สั้นที่สุดเสมอ

ด้วยเหตุนี้เราจึงสามารถสรุปได้ว่า ถ้ากราฟมี cycle แล้ว อัลกอริทึมข้างบนจะตอบความยาวของ cycle ที่สั้นที่สุดมาเสมอ

เราเห็นได้ชัดว่าการทำงานในขั้นตอนที่ 1 ของอัลกอริทึมข้างบนใช้เวลา $O(|V|^{3})\,$ และการทำงานขั้นที่สองใช้เวลา $O(|E|)=O(|V^{2}|)\,$ ดังนั้นอัลกอริทึมข้างบนจึงทำงานได้ในเวลา $O(|V|^{3})\,$