Cardcaptor: หน้าที่ถูกสร้างด้วย 'อัลกอริทึมสำหรับหา cycle ที่สั้นที่สุดที่มี edge $e \,$ …'

2009-10-04T12:01:16Z

หน้าที่ถูกสร้างด้วย 'อัลกอริทึมสำหรับหา cycle ที่สั้นที่สุดที่มี edge <math>e \,</math>…'

หน้าใหม่

อัลกอริทึมสำหรับหา cycle ที่สั้นที่สุดที่มี edge <math>e \,</math> เป็นส่วนประกอบ มีดังต่อไปนี้
# ตัด edge <math>e \,</math> ออกจากกราฟ
# สมมติว่า <math>e = \{u,v\} \,</math> ให้ทำการหา shortest path จาก <math>u \,</math> ไปยัง <math>v \,</math> ในกราฟที่ตัด <math>e \,</math> ออกไปแล้ว ด้วย Dijkstra's algorithm
# คืนผลบวกความยาวของ cycle ในข้อ 2 กับ <math>\ell_e \,</math> เป็นคำตอบ

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

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

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

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

Cardcaptor: หน้าที่ถูกสร้างด้วย 'อัลกอริทึมสำหรับหา cycle ที่สั้นที่สุดที่มี edge e \,…'

Cardcaptor: หน้าที่ถูกสร้างด้วย 'อัลกอริทึมสำหรับหา cycle ที่สั้นที่สุดที่มี edge $e \,$ …'