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

แม่แบบ:ต้องการอ้างอิง แม่แบบ:รายละเอียดทางขั้นตอนวิธี

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

ขั้นตอนวิธี

กำหนดให้ปมหนึ่งเป็นปมเริ่มต้น (initial node) และกำหนดให้ "ระยะทางของปม Y" (distance of node Y) หมายถึงระยะทางจากปมเริ่มต้นไปยังปม Y ขั้นตอนวิธีของไดก์สตราจะกำหนดค่าระยะทางเริ่มต้นไว้บางปมและจะเพิ่มค่าไปทีละขั้นตอน

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

การประยุกต์ใช้งาน

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

ดูเพิ่ม

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

อ้างอิง

แหล่งข้อมูลอื่น

ขั้นตอนวิธีของไดก์สตราในยูทูบ

แม่แบบ:โครง

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

เนื้อหา