Cardcaptor เมื่อ 15:49, 18 กันยายน 2552

2009-09-18T15:49:39Z

Cardcaptor: หน้าที่ถูกสร้างด้วย '== อัลกอริทึม == สมมติให้ $e = (u,v) \,$ เราจะทำการหา simple cycle …'

2009-09-18T15:49:27Z

หน้าที่ถูกสร้างด้วย '== อัลกอริทึม == สมมติให้ <math>e = (u,v) \,</math> เราจะทำการหา simple cycle …'

หน้าใหม่

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

# ตัด <math>e \,</math> ออกจากกราฟ
# หา shortest path P จาก <math>v \,</math> ไปยัง <math>u \,</math>
# ตอบ cycle ที่เกิดจากการนำ <math>(u,v) \,</math> เข้าไปรวมกับ <math>P \,</math>

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

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

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 15:49, 18 กันยายน 2552
แถว 1:		แถว 1:
−	~~== อัลกอริทึม ==~~
	สมมติให้ <math>e = (u,v) \,</math> เราจะทำการหา simple cycle ที่สั้นที่สุดที่มี edge <math>e \,</math> ได้ด้วยอัลกอริทึมต่อไปนี้		สมมติให้ <math>e = (u,v) \,</math> เราจะทำการหา simple cycle ที่สั้นที่สุดที่มี edge <math>e \,</math> ได้ด้วยอัลกอริทึมต่อไปนี้

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

Cardcaptor เมื่อ 15:49, 18 กันยายน 2552

Cardcaptor: หน้าที่ถูกสร้างด้วย '== อัลกอริทึม == สมมติให้ e = (u,v) \, เราจะทำการหา simple cycle …'

Cardcaptor: หน้าที่ถูกสร้างด้วย '== อัลกอริทึม == สมมติให้ $e = (u,v) \,$ เราจะทำการหา simple cycle …'