ขั้นตอนวิธีของไดก์สตรา
จากวิกิพีเดีย สารานุกรมเสรี
 |
บทความนี้ไม่มีการอ้างอิงจากเอกสารอ้างอิงหรือแหล่งข้อมูล โปรดช่วยพัฒนาบทความนี้โดยเพิ่มแหล่งข้อมูลน่าเชื่อถือ เนื้อหาที่ไม่มีการอ้างอิงอาจถูกคัดค้านหรือนำออก |
รูปภาพแสดงขั้นตอนวิธีของไดก์สตรา
|
|
| ประเภท | ขั้นตอนวิธีการค้นหา |
|---|---|
| โครงสร้างข้อมูล | กราฟ |
| ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด | |
ขั้นตอนวิธีของไดก์สตรา (อังกฤษ: Dijkstra's algorithm) ถูกคิดค้นขึ้นโดยนักวิทยาการคอมพิวเตอร์ชาวดัตช์นามว่า แอ็ดส์เคอร์ ไดก์สตรา (Edsger Dijkstra) ในปี 1959 เพื่อแก้ไขปัญหาวิถีสั้นสุดจากจุดหนึ่งใด ๆ สำหรับกราฟที่มีความยาวของเส้นเชื่อมไม่เป็นลบ สำหรับขั้นตอนวิธีนี้จะหาระยะทางสั้นที่สุดจากจุดหนึ่งไปยังจุดใด ๆ ในกราฟโดยจะหาเส้นทางที่สั้นที่สุดไปทีละจุดยอดเรื่อย ๆ จนครบตามที่ต้องการ
ขั้นตอนวิธี[แก้]
กำหนดให้ปมหนึ่งเป็นปมเริ่มต้น (initial node) และกำหนดให้ "ระยะทางของปม Y" (distance of node Y) หมายถึงระยะทางจากปมเริ่มต้นไปยังปม Y ขั้นตอนวิธีของไดก์สตราจะกำหนดค่าระยะทางเริ่มต้นไว้บางปมและจะเพิ่มค่าไปทีละขั้นตอน
- กำหนดให้ทุกปมมีค่าระยะทางตามเส้นเชื่อม โดยให้ปมเริ่มต้นมีค่าเป็นศูนย์ และปมอื่นมีค่าเป็นอนันต์
- ทำเครื่องหมายทุกปมยกเว้นปมเริ่มต้นว่ายังไม่ไปเยือน (unvisited) ตั้งให้ปมเริ่มต้นเป็นปมปัจจุบัน สร้างเซตของปมที่ยังไม่ไปเยือนขึ้นมาเซตหนึ่งซึ่งประกอบด้วยทุกปมยกเว้นปมเริ่มต้น
- จากปมปัจจุบัน พิจารณาปมข้างเคียงตามเส้นเชื่อมทุกปมที่ยังไม่ไปเยือน และคำนวณระยะทางต่อเนื่องของเส้นเชื่อม ตัวอย่างเช่น ถ้าปมปัจจุบันคือ A มีระยะทางของปมเป็น 6 และเส้นเชื่อมที่ต่อจาก A ไปยังปมข้างเคียง B มีระยะทางเป็น 2 ดังนั้นระยะทางของปม B (โดยผ่าน A) จึงเท่ากับ 6+2=8 เป็นต้น ถ้าระยะทางที่คำนวณได้มีค่าน้อยกว่าค่าระยะทางที่บันทึกอยู่ของปมนั้น ให้เขียนทับค่าระยะทางของปมดังกล่าว แม้ว่าปมข้างเคียงได้ถูกพิจารณาแล้ว แต่ก็ยังไม่ทำเครื่องหมายว่าไปเยือนแล้ว (visited) ในขั้นตอนนี้ ปมข้างเคียงจะยังคงอยู่ในเซตของปมที่ยังไม่ไปเยือนเช่นเดิม
- เมื่อพิจารณาปมข้างเคียงจากปมปัจจุบันครบทุกปมแล้ว ทำเครื่องหมายปมปัจจุบันว่าไปเยือนแล้ว และนำออกจากเซตของปมที่ยังไม่ไปเยือน ปมที่ไปเยือนแล้วนี้จะไม่ถูกนำมาตรวจสอบอีก ค่าระยะทางที่บันทึกอยู่จะสิ้นสุดและมีค่าน้อยสุด
- ปมปัจจุบันตัวถัดไปที่ถูกเลือกจะเป็นปมที่มีค่าระยะทางน้อยสุดในเซตของปมที่ยังไม่ไปเยือน
- ถ้าเซตของปมที่ยังไม่ไปเยือนฟว่างแล้วให้หยุดการทำงาน ขั้นตอนวิธีเสร็จสิ้น หากไม่ใช่ให้เลือกปมยังไม่ไปเยือนที่มีค่าระยะทางน้อยสุดเป็นปมปัจจุบัน แล้ววนกลับไปทำขั้นตอนที่ 3
การประยุกต์ใช้งาน[แก้]
เราสามารถย่อส่วนปัญหาในชีวิตจริงให้เป็นปัญหาทางคณิตศาสตร์ได้ เช่น การให้จุดยอดเป็นเมืองและเส้นเชื่อมเป็นถนน
ดูเพิ่ม[แก้]
- ขั้นตอนวิธีของเบลแมน-ฟอร์ด สำหรับปัญหาวิถีสั้นสุดที่น้ำหนักของเส้นเชื่อมติดลบได้
- ปัญหาการเดินทางของพนักงานขาย
อ้างอิง[แก้]
- Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs". Numerische Mathematik 1: 269–271. doi:10.1007/BF01386390.
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Section 24.3: Dijkstra's algorithm". Introduction to Algorithms (Second ed.). MIT Press and McGraw-Hill. pp. 595–601. ISBN 0-262-03293-7.
- Fredman, Michael Lawrence; Tarjan, Robert E. (1984). "Fibonacci heaps and their uses in improved network optimization algorithms". 25th Annual Symposium on Foundations of Computer Science (IEEE): 338–346. doi:10.1109/SFCS.1984.715934.
- Fredman, Michael Lawrence; Tarjan, Robert E. (1987). "Fibonacci heaps and their uses in improved network optimization algorithms". Journal of the Association for Computing Machinery 34 (3): 596–615. doi:10.1145/28869.28874.
- Zhan, F. Benjamin; Noon, Charles E. (February 1998). "Shortest Path Algorithms: An Evaluation Using Real Road Networks". Transportation Science 32 (1): 65–73. doi:10.1287/trsc.32.1.65.
- Leyzorek, M.; Gray, R. S.; Johnson, A. A.; Ladew, W. C.; Meaker, Jr., S. R.; Petry, R. M.; Seitz, R. N. (1957). Investigation of Model Techniques — First Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques for Communication Systems. Cleveland, Ohio: Case Institute of Technology.
