ขั้นตอนวิธีของ Dijkstra
- ผู้เสนอ
- Edsger W. Dijkstra
- ปี
- 1956
- ประเภท
- algorithm
- กลุ่มวิธี
- Graph Algorithms
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
ขั้นตอนวิธีของ Dijkstra ซึ่งนำเสนอโดย Edsger W. Dijkstra ในปี ค.ศ. 1956 เป็นหนึ่งในขั้นตอนวิธีพื้นฐานที่สุดในวิทยาการคอมพิวเตอร์สำหรับการแก้ปัญหาเส้นทางที่สั้นที่สุดจากแหล่งกำเนิดเดียว (single-source shortest path problem) โดยจะค้นหาเส้นทางที่สั้นที่สุดจากจุดเริ่มต้นไปยังจุดอื่น ๆ ทั้งหมดในกราฟถ่วงน้ำหนักที่มีน้ำหนักขอบไม่เป็นลบ
แนวคิดเบื้องหลังวิธีการ
ขั้นตอนวิธีนี้จะรักษากลุ่มของจุดยอดที่ทราบระยะทางที่สั้นที่สุดจากแหล่งกำเนิดแล้ว และขยายกลุ่มนี้ซ้ำ ๆ โดยการเลือกจุดยอดที่ยังไม่ถูกประมวลผลที่ใกล้ที่สุด และอัปเดตระยะทางไปยังจุดยอดข้างเคียง หลักการสำคัญคือคุณสมบัติแบบละโมบ (greedy property): เมื่อจุดยอดถูกเลือกแล้ว ระยะทางจากแหล่งกำเนิดจะถือเป็นที่สิ้นสุด เนื่องจากน้ำหนักขอบทั้งหมดไม่เป็นลบ ดังนั้นเส้นทางที่ยาวกว่าผ่านจุดยอดที่ยังไม่ถูกเยี่ยมชมจึงไม่สามารถสั้นกว่าได้ ซึ่งรับประกันความถูกต้องและเหมาะสมที่สุด
ประวัติศาสตร์
Edsger W. Dijkstra ได้ตีพิมพ์ขั้นตอนวิธีของเขาในปี ค.ศ. 1959 ในบทความสามหน้าซึ่งกลายเป็นหนึ่งในผลงานที่มีการอ้างอิงมากที่สุดในวิทยาการคอมพิวเตอร์ ขั้นตอนวิธีนี้เกิดขึ้นจากงานของ Dijkstra บนคอมพิวเตอร์ ARMAC ในอัมสเตอร์ดัม ตลอดหลายทศวรรษ มีการปรับปรุงมากมาย รวมถึงโครงสร้างข้อมูลที่ดีขึ้น (ฮีปแบบ Fibonacci ที่มีความซับซ้อน O(E+VlogV)) และรูปแบบสองทิศทาง ขั้นตอนวิธีนี้ยังคงเป็นหัวใจสำคัญของโปรโตคอลการกำหนดเส้นทางสมัยใหม่ เช่น OSPF ในเครือข่าย
ควรใช้เมื่อใด
ประยุกต์ใช้ขั้นตอนวิธีของ Dijkstra เมื่อค้นหาเส้นทางที่สั้นที่สุดในกราฟที่มีน้ำหนักขอบไม่เป็นลบ เหมาะสำหรับระบบนำทาง การกำหนดเส้นทางเครือข่าย และปัญหาเกี่ยวกับกราฟใด ๆ ที่ต้องการเส้นทางที่เหมาะสมที่สุด ใช้สำหรับเส้นทางที่สั้นที่สุดจากแหล่งกำเนิดเดียวไปยังจุดยอดทั้งหมด สำหรับกราฟที่มีน้ำหนักติดลบ ให้ใช้ Bellman-Ford แทน สำหรับการค้นหาแบบสองทิศทางหรือการนำทางแบบฮิวริสติก ให้พิจารณาขั้นตอนวิธี A*
ข้อจำกัดและข้อควรพิจารณา
- ไม่สามารถจัดการกับกราฟที่มีน้ำหนักขอบติดลบได้
- คำนวณเส้นทางที่สั้นที่สุดไปยังจุดยอดทั้งหมด ไม่ใช่แค่ปลายทางเดียว (แม้ว่าจะสามารถสิ้นสุดได้ก่อนเวลาอันควร)
- มีประสิทธิภาพน้อยกว่า A* เมื่อมีข้อมูลฮิวริสติก
- ต้องค้นพบจุดยอดทั้งหมด; ไม่มีประสิทธิภาพสำหรับการเชื่อมต่อที่เบาบางมาก
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- เข้าใจและนำไปใช้ได้ง่าย พร้อมการรับประกันความถูกต้องที่ชัดเจน
- มีประสิทธิภาพด้วยโครงสร้างข้อมูลที่เหมาะสม: O((V+E)logV) ด้วยฮีปแบบไบนารี, O(V²) ด้วยอาร์เรย์
- เหมาะสมที่สุดสำหรับกราฟน้ำหนักไม่เป็นลบ; พิสูจน์ความเหมาะสมที่สุดของเส้นทางที่คำนวณได้
- ทำงานได้ทั้งกราฟมีทิศทางและไม่มีทิศทาง
- เป็นรากฐานสำหรับการขยายและขั้นตอนวิธีที่เกี่ยวข้องจำนวนมาก
การประยุกต์ใช้
- ระบบ GPS และระบบนำทาง: การค้นหาเส้นทางที่สั้นที่สุดสำหรับยานพาหนะและคนเดินเท้า
- โปรโตคอลการกำหนดเส้นทางเครือข่าย: การกำหนดเส้นทางที่เหมาะสมที่สุดสำหรับแพ็กเก็ตข้อมูลในเครือข่ายคอมพิวเตอร์
- เครือข่ายสังคม: การค้นหาเส้นทางการเชื่อมต่อที่สั้นที่สุดระหว่างผู้ใช้หรือผู้มีอิทธิพล
- การพัฒนาเกม: การค้นหาเส้นทางสำหรับปัญญาประดิษฐ์และการเคลื่อนที่ของตัวละครที่ไม่ใช่ผู้เล่น
- การวางแผนการเคลื่อนที่ของหุ่นยนต์: การคำนวณวิถีที่เหมาะสมที่สุดสำหรับระบบหุ่นยนต์
- โทรคมนาคม: การเพิ่มประสิทธิภาพการกำหนดเส้นทางการโทรและเส้นทางการแพร่กระจายสัญญาณ
วิธีการทำงาน
วิธีการทำงาน
กำหนดระยะทางไปยังแหล่งกำเนิดเป็นศูนย์ และระยะทางอื่น ๆ ทั้งหมดเป็นอนันต์ ทำเครื่องหมายจุดยอดทั้งหมดว่ายังไม่ถูกเยี่ยมชม และสร้างคิวลำดับความสำคัญ
เลือกจุดยอดที่ยังไม่ถูกเยี่ยมชมที่มีระยะทางน้อยที่สุดจากแหล่งกำเนิดโดยใช้คิวลำดับความสำคัญ
สำหรับจุดยอดข้างเคียงแต่ละจุดของจุดยอดที่เลือก หากเส้นทางผ่านจุดยอดที่เลือกให้ระยะทางที่สั้นกว่า ให้อัปเดตระยะทางของจุดยอดข้างเคียงและเพิ่มลงในคิวลำดับความสำคัญ
ข้อผิดพลาดที่พบบ่อย
- การใช้ขั้นตอนวิธีกับกราฟที่มีน้ำหนักติดลบ ส่งผลให้ได้เส้นทางที่สั้นที่สุดที่ไม่ถูกต้อง
- การนำไปใช้ที่ไม่มีประสิทธิภาพด้วยการดำเนินการ extract-min แบบเชิงเส้น ทำให้ประสิทธิภาพต่ำ
- การไม่อัปเดตระยะทางอย่างถูกต้องเมื่อมีการเยี่ยมชมจุดยอดข้างเคียงซ้ำผ่านเส้นทางที่แตกต่างกัน
คำถามที่พบบ่อย
เหตุใดขั้นตอนวิธีของ Dijkstra จึงล้มเหลวกับน้ำหนักติดลบ?
ขั้นตอนวิธีนี้สมมติว่าเมื่อจุดยอดถูกสรุปแล้ว จะไม่สามารถพบเส้นทางที่สั้นกว่าผ่านจุดยอดที่ยังไม่ถูกเยี่ยมชมได้ ด้วยน้ำหนักติดลบ เส้นทางที่ยาวกว่าอาจดีขึ้นในภายหลังเมื่อมีการใช้ขอบติดลบ ซึ่งละเมิดข้อสมมตินี้
ควรใช้โครงสร้างข้อมูลใดสำหรับคิวลำดับความสำคัญ?
ฮีปแบบไบนารีให้การดำเนินการ O(logV) สำหรับทั้งการแทรกและการดึงออก ส่งผลให้มีความซับซ้อนรวม O((V+E)logV) ฮีปแบบ Fibonacci มีความซับซ้อน O(E+VlogV) แต่มีค่าคงที่ขนาดใหญ่ อาร์เรย์ทำงานได้ดีสำหรับกราฟขนาดเล็ก
ขั้นตอนวิธีของ Dijkstra สามารถค้นหาเส้นทางไปยังปลายทางที่เฉพาะเจาะจงได้อย่างไร?
ยุติขั้นตอนวิธีทันทีที่จุดยอดปลายทางถูกเลือก (ระยะทางของมันถูกสรุปแล้ว) เพื่อหลีกเลี่ยงการคำนวณที่ไม่จำเป็น อีกทางหนึ่งคือสร้างเส้นทางขึ้นใหม่โดยการรักษาตัวชี้แม่ (parent pointers) ระหว่างการดำเนินการ
ขั้นตอนวิธีของ Dijkstra สามารถใช้ในกราฟไม่มีทิศทางได้หรือไม่?
ได้ กราฟไม่มีทิศทางสามารถแสดงเป็นกราฟมีทิศทางได้ โดยมีขอบทั้งสองทิศทางสำหรับแต่ละขอบที่ไม่มีทิศทาง โดยแต่ละขอบมีน้ำหนักเท่ากัน ขั้นตอนวิธีนี้ทำงานเหมือนกันบนการแสดงแบบสองทิศทาง
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วCormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
ISBN: 978-0-262-03384-8คัดลอกแล้ว