ขั้นตอนวิธีของไดก์สตรา

ขั้นตอนวิธีของไดก์สตรา () ถูกคิดค้นขึ้นโดยนักวิทยาการคอมพิวเตอร์ชาวดัตช์นามว่า แอ็ดส์เคอร์ ไดก์สตรา (Edsger Dijkstra) ในปี 1959 เพื่อแก้ไขปัญหาวิถีสั้นสุดจากจุดหนึ่งใด ๆ สำหรับกราฟที่มีความยาวของเส้นเชื่อมไม่เป็นลบ สำหรับขั้นตอนวิธีนี้จะหาระยะทางสั้นที่สุดจากจุดหนึ่งไปยังจุดใด ๆ ในกราฟโดยจะหาเส้นทางที่สั้นที่สุดไปทีละจุดยอดเรื่อย ๆ จนครบตามที่ต้องการ

 ขั้นตอนวิธี 
กำหนดให้ปมหนึ่งเป็นปมเริ่มต้น (initial node) และกำหนดให้ "ระยะทางของปม Y" (distance of node Y) หมายถึงระยะทางจากปมเริ่มต้นไปยังปม Y ขั้นตอนวิธีของไดก์สตราจะกำหนดค่าระยะทางเริ่มต้นไว้บางปมและจะเพิ่มค่าไปทีละขั้นตอน
 กำหนดให้ทุกปมมีค่าระยะทางตามเส้นเชื่อม โดยให้ปมเริ่มต้นมีค่าเป็นศูนย์ และปมอื่นมีค่าเป็นอนันต์
 ทำเครื่องหมายทุกปมยกเว้นปมเริ่มต้นว่ายังไม่ไปเยือน (unvisited) ตั้งให้ปมเริ่มต้นเป็นปมปัจจุบัน สร้างเซตของปมที่ยังไม่ไปเยือนขึ้นมาเซตหนึ่งซึ่งประกอบด้วยทุกปมยกเว้นปมเริ่มต้น
 จากปมปัจจุบัน พิจารณาปมข้างเคียงตามเส้นเชื่อมทุกปมที่ยังไม่ไปเยือน และคำนวณระยะทางต่อเนื่องของเส้นเชื่อม ตัวอย่างเช่น ถ้าปมปัจจุบันคือ A มีระยะทางของปมเป็น 6 และเส้นเชื่อมที่ต่อจาก A ไปยังปมข้างเคียง B มีระยะทางเป็น 2 ดังนั้นระยะทางของปม B (โดยผ่าน A) จึงเท่ากับ 6+2=8 เป็นต้น ถ้าระยะทางที่คำนวณได้มีค่าน้อยกว่าค่าระยะทางที่บันทึกอยู่ของปมนั้น ให้เขียนทับค่าระยะทางของปมดังกล่าว แม้ว่าปมข้างเคียงได้ถูกพิจารณาแล้ว แต่ก็ยังไม่ทำเครื่องหมายว่าไปเยือนแล้ว (visited) ในขั้นตอนนี้ ปมข้างเคียงจะยังคงอยู่ในเซตของปมที่ยังไม่ไปเยือนเช่นเดิม
 เมื่อพิจารณาปมข้างเคียงจากปมปัจจุบันครบทุกปมแล้ว ทำเครื่องหมายปมปัจจุบันว่าไปเยือนแล้ว และนำออกจากเซตของปมที่ยังไม่ไปเยือน ปมที่ไปเยือนแล้วนี้จะไม่ถูกนำมาตรวจสอบอีก ค่าระยะทางที่บันทึกอยู่จะสิ้นสุดและมีค่าน้อยสุด
 ปมปัจจุบันตัวถัดไปที่ถูกเลือกจะเป็นปมที่มีค่าระยะทางน้อยสุดในเซตของปมที่ยังไม่ไปเยือน
 ถ้าเซตของปมที่ยังไม่ไปเยือนฟว่างแล้วให้หยุดการทำงาน ขั้นตอนวิธีเสร็จสิ้น หากไม่ใช่ให้เลือกปมยังไม่ไปเยือนที่มีค่าระยะทางน้อยสุดเป็นปมปัจจุบัน แล้ววนกลับไปทำขั้นตอนที่ 3 
 การประยุกต์ใช้งาน 
เราสามารถย่อส่วนปัญหาในชีวิตจริงให้เป็นปัญหาทางคณิตศาสตร์ได้ เช่น การให้จุดยอดเป็นเมืองและเส้นเชื่อมเป็นถนน

 ดูเพิ่ม 
 ขั้นตอนวิธีของเบลแมน-ฟอร์ด สำหรับปัญหาวิถีสั้นสุดที่น้ำหนักของเส้นเชื่อมติดลบได้
 ปัญหาการเดินทางของพนักงานขาย

 อ้างอิง 












 แหล่งข้อมูลอื่น 
 ขั้นตอนวิธีของไดก์สตราในยูทูบ

หมวดหมู่:ขั้นตอนวิธีการค้นหา
หมวดหมู่:ขั้นตอนวิธีกราฟ