418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต II/เฉลยข้อ 3
อัลกอริทึมในการหา cycle ที่สั้นที่สุดมีดังต่อไปนี้
- รัน Floyd's algorithm บนกราฟ และสมมติให้ output ของมันอยู่ในอะเรย์
- สำหรับ edge แต่ละ edge ใน ให้คำนวณค่า โดยที่ คือความยาวของ edge แล้วจำค่า ที่ต่ำสุดเอาไว้
- ถ้าค่าที่ต่ำที่สุดในข้อ 2 เป็น ก็ให้ตอบว่าไม่มี cycle มิเช่นนั้นให้คืนมันเป็นคำตอบ
เราสามารถแสดงว่าคำตอบของอัลกอริทึมข้างบนคืนมาเป็นความยาวของ cycle ที่สั้นสุด ได้ดังต่อไปนี้
กรณีที่ 1: ถ้ากราฟไม่มี cycle เราจะได้ว่าสำหรับทุกๆ edge จะไม่มี path จาก ไปยัง ดังนั้น เสมอ ด้วยเหตุนี้ค่า ที่ต่ำที่สุดจึงมีค่าเท่ากับ และอัลกอริทึมข้างบนจะตอบว่ากราฟไม่มี cycle ได้อย่างถูกต้อง
![{\displaystyle M[v,u]+\ell _{(u,v)}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c503cd24add11ac472d7927581f0e110227586bb)
กรณีที่ 2 ถ้ากราฟมี cycle เราจะได้ว่ามี edge อย่างน้อยหนึ่ง edge ที่ทำให้ มีค่าน้อยกว่า เราจะต้องแสดงว่าค่า ที่น้อยที่สุดคือความยาวของ cycle ที่สั้นที่สุด
อันดับแรก ให้พิจารณา edge ใดๆ เราได้ว่า คือความยาวของ shortest path จาก ไปยัง ด้วยเหตุนี้ จึงเป็นความยาวของ cycle ที่สั้นที่สุดที่มี edge (เราสามารถแสดงว่าข้อความสุดท้ายนี้เป็นจริงได้โดยการสมมติให้เกิดข้อขัดแย้งว่า ไม่ใช่ความยาวของ cycle ที่สั้นที่สุดที่มี edge แต่เราจะได้ว่า cycle นั้นจะต้องมี path จาก ไปยัง และไม่มี path จาก v ไป u ที่มีความยาวน้อยกว่า แล้ว ทำให้เกิดข้อขัดแย้งขึ้น)
อันดับที่สอง เนื่องจาก cycle ที่สั้นที่สุดจะต้องผ่าน edge อย่างน้อย 1 edge เราจึงได้ว่าการนำความยาว cycle ที่สั้นที่สุดที่ผ่าน edge แต่ละ edge มาเปรียบเทียบกัน เพื่อหาความยาวที่น้อยที่สุดจะทำให้เราได้ความยาวของ cycle ที่สั้นที่สุดเสมอ
ด้วยเหตุนี้เราจึงสามารถสรุปได้ว่า ถ้ากราฟมี cycle แล้ว อัลกอริทึมข้างบนจะตอบความยาวของ cycle ที่สั้นที่สุดมาเสมอ
เราเห็นได้ชัดว่าการทำงานในขั้นตอนที่ 1 ของอัลกอริทึมข้างบนใช้เวลา และการทำงานขั้นที่สองใช้เวลา ดังนั้นอัลกอริทึมข้างบนจึงทำงานได้ในเวลา
