Skip to content
กลับไปยังผลการค้นหา

ขั้นตอนวิธีของ 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 และระบบนำทาง: การค้นหาเส้นทางที่สั้นที่สุดสำหรับยานพาหนะและคนเดินเท้า
  • โปรโตคอลการกำหนดเส้นทางเครือข่าย: การกำหนดเส้นทางที่เหมาะสมที่สุดสำหรับแพ็กเก็ตข้อมูลในเครือข่ายคอมพิวเตอร์
  • เครือข่ายสังคม: การค้นหาเส้นทางการเชื่อมต่อที่สั้นที่สุดระหว่างผู้ใช้หรือผู้มีอิทธิพล
  • การพัฒนาเกม: การค้นหาเส้นทางสำหรับปัญญาประดิษฐ์และการเคลื่อนที่ของตัวละครที่ไม่ใช่ผู้เล่น
  • การวางแผนการเคลื่อนที่ของหุ่นยนต์: การคำนวณวิถีที่เหมาะสมที่สุดสำหรับระบบหุ่นยนต์
  • โทรคมนาคม: การเพิ่มประสิทธิภาพการกำหนดเส้นทางการโทรและเส้นทางการแพร่กระจายสัญญาณ

วิธีการทำงาน

วิธีการทำงาน

1

กำหนดระยะทางไปยังแหล่งกำเนิดเป็นศูนย์ และระยะทางอื่น ๆ ทั้งหมดเป็นอนันต์ ทำเครื่องหมายจุดยอดทั้งหมดว่ายังไม่ถูกเยี่ยมชม และสร้างคิวลำดับความสำคัญ

2

เลือกจุดยอดที่ยังไม่ถูกเยี่ยมชมที่มีระยะทางน้อยที่สุดจากแหล่งกำเนิดโดยใช้คิวลำดับความสำคัญ

3

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

ข้อผิดพลาดที่พบบ่อย

  • การใช้ขั้นตอนวิธีกับกราฟที่มีน้ำหนักติดลบ ส่งผลให้ได้เส้นทางที่สั้นที่สุดที่ไม่ถูกต้อง
  • การนำไปใช้ที่ไม่มีประสิทธิภาพด้วยการดำเนินการ extract-min แบบเชิงเส้น ทำให้ประสิทธิภาพต่ำ
  • การไม่อัปเดตระยะทางอย่างถูกต้องเมื่อมีการเยี่ยมชมจุดยอดข้างเคียงซ้ำผ่านเส้นทางที่แตกต่างกัน

คำถามที่พบบ่อย

เหตุใดขั้นตอนวิธีของ Dijkstra จึงล้มเหลวกับน้ำหนักติดลบ?

ขั้นตอนวิธีนี้สมมติว่าเมื่อจุดยอดถูกสรุปแล้ว จะไม่สามารถพบเส้นทางที่สั้นกว่าผ่านจุดยอดที่ยังไม่ถูกเยี่ยมชมได้ ด้วยน้ำหนักติดลบ เส้นทางที่ยาวกว่าอาจดีขึ้นในภายหลังเมื่อมีการใช้ขอบติดลบ ซึ่งละเมิดข้อสมมตินี้

ควรใช้โครงสร้างข้อมูลใดสำหรับคิวลำดับความสำคัญ?

ฮีปแบบไบนารีให้การดำเนินการ O(logV) สำหรับทั้งการแทรกและการดึงออก ส่งผลให้มีความซับซ้อนรวม O((V+E)logV) ฮีปแบบ Fibonacci มีความซับซ้อน O(E+VlogV) แต่มีค่าคงที่ขนาดใหญ่ อาร์เรย์ทำงานได้ดีสำหรับกราฟขนาดเล็ก

ขั้นตอนวิธีของ Dijkstra สามารถค้นหาเส้นทางไปยังปลายทางที่เฉพาะเจาะจงได้อย่างไร?

ยุติขั้นตอนวิธีทันทีที่จุดยอดปลายทางถูกเลือก (ระยะทางของมันถูกสรุปแล้ว) เพื่อหลีกเลี่ยงการคำนวณที่ไม่จำเป็น อีกทางหนึ่งคือสร้างเส้นทางขึ้นใหม่โดยการรักษาตัวชี้แม่ (parent pointers) ระหว่างการดำเนินการ

ขั้นตอนวิธีของ Dijkstra สามารถใช้ในกราฟไม่มีทิศทางได้หรือไม่?

ได้ กราฟไม่มีทิศทางสามารถแสดงเป็นกราฟมีทิศทางได้ โดยมีขอบทั้งสองทิศทางสำหรับแต่ละขอบที่ไม่มีทิศทาง โดยแต่ละขอบมีน้ำหนักเท่ากัน ขั้นตอนวิธีนี้ทำงานเหมือนกันบนการแสดงแบบสองทิศทาง

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. 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
    คัดลอกแล้ว