หมายเหตุ ผู้เขียนแนะนำให้อ่านขั้นตอนแล้วดูรูปภาพประกอบไปด้วยเพราะจะทำให้เข้าใจง่ายมากยิ่งขึ้น
1. กำหนดให้ทุกจุดมีค่าระยะทางตามเส้นเชื่อมโดยให้จุดเริ่มต้นมีค่าเป็นศูนย์ และจุดอื่นๆมีค่าเป็นอนันต์
2. ตั้งให้จุดที่เป็นจุดเริ่มต้น เป็นจุดปัจจุบัน และให้ทำเครื่องหมายไว้ว่าจุดอื่นๆนั้นเป็นจุดที่ยังไม่ได้ไปสร้างเซตของจุดที่ยังไปไม่ถึงขึ้นมาเซตหนึ่งซึ่งประกอบด้วยทุกจุดยกเว้นจุดเริ่มต้น
3. จากจุดปัจจุบัน ให้พิจารณาดูจุดข้างเคียงตามเส้นเชื่อมทุกจุดที่ยังไม่ได้ไป และคำนวณระยะทางต่อเนื่องของเส้นเชื่อม ซึ่งจะคำนวณด้วยการนำระยะของจุดปัจจุบันมาบวกกับค่าระยะทางของเส้นเชื่อม
4. เมื่อพิจารณาจุดข้างเคียงจากจุดปัจจุบันครบทุกจุดแล้ว ทำเครื่องหมายจุดปัจจุบันว่าไปถึงแล้ว และนำออกจากเซตของจุดที่ยังไม่ได้ไป ซึ่งจุดที่เราไปถึงแล้ว เราจะไม่นำมาพิจารณาอีก ค่าระยะทางที่บันทึกอยู่จะสิ้นสุดและมีค่าน้อยสุด
5. จุดปัจจุบันตัวถัดไปที่ถูกเลือกจะเป็นปมที่มีค่าระยะทางน้อยสุดในเซตของจุดที่ยังไม่ไปไม่ถึง
6. ถ้าเซตของจุดที่ยังไม่ได้ไปนั้นว่างหรือก็คือเราเดินไปครบทุกจุดแล้วให้หยุดทำ ขั้นตอนวิธีเสร็จสิ้น หากไม่ใช่ให้เลือกจุดที่ยังไม่ได้ไปที่มีค่าระยะทางน้อยสุดเป็นจุดปัจจุบัน แล้ววนกลับไปทำขั้นตอนที่ 3
รูปตัวอย่างจาก https://th.wikipedia.org/wiki/ขั้นตอนวิธีของไดก์สตรา
ถ้าหากผู้อ่าน มีความสับสนอ่านแล้วไม่เข้าใจผู้เขียนแนะนำให้ดูเป็นคลิปวิดิโอจาก Youtube ด้านล่าง เพราะผู้จัดทำคลิปวิดิโอได้สอนอย่างละเอียดทีละขั้นตอน แต่จะไม่เหมือนกับที่ผู้เขียนได้เขียนอยู่เล็กน้อยตรงที่ "ในขั้นตอนวิธีของผู้เขียนนั้นจะเป็นการสร้างเซตจุดที่ยังไม่เคยไป แต่ในวิดิโอจะเป็นการสร้างเซตของจุดที่เคยไปแล้ว" เท่านั้นเอง
ไม่มีความคิดเห็น:
แสดงความคิดเห็น