อัลกอริทึมของไดจ์คสตรา — หาเส้นทางสั้นที่สุดทีละขั้น

อัลกอริทึมของไดจ์คสตราใช้หาเส้นทางสั้นที่สุดจากโหนดเริ่มต้นหนึ่งโหนดในกราฟถ่วงน้ำหนัก ตราบใดที่น้ำหนักของทุกขอบไม่เป็นลบ ถ้าคุณสนใจแค่ปลายทางเดียว ก็หยุดได้ทันทีเมื่อโหนดปลายทางนั้นถูกปิดงานแล้ว

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

อัลกอริทึมของไดจ์คสตราแก้ปัญหาอะไร

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

อัลกอริทึมนี้ใช้ได้ทั้งกับกราฟมีทิศทางและไม่มีทิศทาง เงื่อนไขสำคัญมีชัดเจนคือ น้ำหนักของทุกขอบต้องมีค่าอย่างน้อย $0$

อัลกอริทึมทำงานอย่างไร

แต่ละโหนดจะเก็บระยะทางชั่วคราวจากโหนดเริ่มต้น ตอนเริ่มต้น โหนดเริ่มต้นมีระยะทางเป็น $0$ และโหนดอื่นทุกโหนดมีระยะทางเป็น $\infty$

จากนั้นทำลูปนี้ซ้ำ:

1. เลือกโหนดที่ยังไม่ถูกปิดงานและมีระยะทางชั่วคราวน้อยที่สุด
2. ตรวจสอบเพื่อนบ้านแต่ละโหนดผ่านโหนดนั้น
3. ถ้าเส้นทางใหม่มีต้นทุนต่ำกว่า ให้อัปเดตระยะทางของเพื่อนบ้าน
4. ทำเครื่องหมายโหนดปัจจุบันว่าปิดงานแล้ว

ขั้นตอนที่ 3 เรียกว่า relaxation หรือการผ่อนคลาย เมื่อโหนดถูกปิดงานแล้วถือว่าเสร็จสมบูรณ์ นั่นคือระยะทางสั้นที่สุดของมันเป็นค่าที่แน่นอนแล้ว ตราบใดที่กราฟไม่มีขอบที่มีน้ำหนักติดลบ

อัลกอริทึมของไดจ์คสตราทีละขั้น

นี่คือขั้นตอนทั้งหมดแบบย่อ:

1. เลือกโหนดเริ่มต้น
2. กำหนดระยะทางของมันเป็น $0$ และระยะทางของโหนดอื่นทุกโหนดเป็น $\infty$
3. เลือกโหนดที่ยังไม่ถูกปิดงานและมีระยะทางชั่วคราวน้อยที่สุด
4. ผ่อนคลายขอบขาออกของโหนดนั้น
5. ทำเครื่องหมายโหนดนั้นว่าปิดงานแล้ว
6. ทำซ้ำจนกว่าโหนดที่เข้าถึงได้ทั้งหมดจะถูกปิดงาน หรือหยุดเมื่อโหนดเป้าหมายของคุณถูกปิดงานแล้ว

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

ตัวอย่างการหาเส้นทางสั้นที่สุด

สมมติว่ากราฟมีน้ำหนักขอบดังนี้:

• $A \to B = 4$
• $A \to C = 1$
• $C \to B = 2$
• $B \to D = 1$
• $C \to D = 5$

เราต้องการหาเส้นทางสั้นที่สุดจาก $A$ ไป $D$

เริ่มต้นด้วย:

$$\text{dist}(A)=0,\quad \text{dist}(B)=\infty,\quad \text{dist}(C)=\infty,\quad \text{dist}(D)=\infty$$

ปิดงาน $A$ ก่อน แล้วผ่อนคลายขอบของมัน:

$$\text{dist}(B)=4,\quad \text{dist}(C)=1$$

ตอนนี้ระยะทางที่น้อยที่สุดในบรรดาโหนดที่ยังไม่ถูกปิดงานอยู่ที่ $C$ ดังนั้นให้ปิดงาน $C$ เป็นลำดับถัดไป

เมื่อผ่าน $C$:

• ผ่าน $C$ เส้นทางไป $B$ มีต้นทุน $1+2=3$ ซึ่งดีกว่า $4$ ดังนั้นอัปเดต $\text{dist}(B)=3$
• ผ่าน $C$ เส้นทางไป $D$ มีต้นทุน $1+5=6$ ดังนั้นกำหนด $\text{dist}(D)=6$

ตอนนี้ $B$ มีระยะทางน้อยที่สุดในบรรดาโหนดที่ยังไม่ถูกปิดงาน ดังนั้นให้ปิดงาน $B$

เมื่อผ่าน $B$ เส้นทางไป $D$ มีต้นทุนเป็น:

$$3+1=4$$

ค่านี้ดีกว่า $6$ ดังนั้นอัปเดต $\text{dist}(D)$ จาก $6$ เป็น $4$

ตอนนี้ $D$ เป็นโหนดที่ยังไม่ถูกปิดงานและมีระยะทางน้อยที่สุด ให้ปิดงานมัน แล้วหยุด

เส้นทางสั้นที่สุดคือ:

$$A \to C \to B \to D$$

โดยมีต้นทุนรวมเป็น:

$$1+2+1=4$$

ตัวอย่างนี้แสดงรูปแบบสำคัญอย่างหนึ่ง คือเส้นทางที่ตอนแรกดูแย่กว่าอย่าง $A \to B$ กลับดีขึ้นได้ในภายหลังเมื่อผ่าน $C$ อัลกอริทึมของไดจ์คสตราอนุญาตให้เกิดสิ่งนี้ได้ตราบใดที่ $B$ ยังไม่ถูกปิดงาน เมื่อโหนดใดถูกปิดงานแล้ว ระยะทางของมันจะไม่เปลี่ยนอีก

ทำไมน้ำหนักไม่ติดลบจึงสำคัญ

สมมติว่าโหนดที่ยังไม่ถูกปิดงานและมีต้นทุนต่ำที่สุดในตอนนี้มีระยะทางเป็น $d$ เส้นทางใหม่ใด ๆ ที่จะมาถึงโหนดนั้นในภายหลัง ต้องมาจากโหนดที่ยังไม่ถูกปิดงานอีกโหนดหนึ่งซึ่งมีระยะทางชั่วคราวอย่างน้อย $d$ แล้วจึงบวกด้วยขอบที่มีน้ำหนักอย่างน้อย $0$

ดังนั้นเส้นทางที่มาทีหลังจึงไม่สามารถดีกว่า $d$ ได้ นี่จึงเป็นเหตุผลว่าทำไมการปิดงานโหนดที่มีระยะทางชั่วคราวน้อยที่สุดจึงปลอดภัย เมื่อทุกน้ำหนักไม่เป็นลบ

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

ข้อผิดพลาดที่พบบ่อยในอัลกอริทึมของไดจ์คสตรา

ใช้กับขอบที่มีน้ำหนักติดลบ

แม้มีขอบติดลบเพียงเส้นเดียวก็ทำให้ตรรกะแบบ greedy พังได้ ถ้ามีน้ำหนักติดลบได้ ควรใช้วิธีหาเส้นทางสั้นที่สุดแบบอื่น

คิดว่า "เคยเห็นแล้ว" เท่ากับ "เสร็จแล้ว"

โหนดหนึ่งอาจมีระยะทางชั่วคราวแล้ว แต่ยังไม่ถือว่าเสร็จ มีเพียงโหนดที่ถูกปิดงานแล้วเท่านั้นที่มีระยะทางสั้นที่สุดเป็นค่าที่แน่นอน

ลืมตารางโหนดก่อนหน้า

ระยะทางบอกต้นทุน แต่ถ้าคุณต้องการเส้นทางจริงด้วย ต้องเก็บว่าโหนดใดเป็นตัวล่าสุดที่ทำให้ระยะทางแต่ละค่าดีขึ้น

อัลกอริทึมของไดจ์คสตราใช้ที่ไหน

อัลกอริทึมของไดจ์คสตราถูกใช้เมื่อปัญหาสามารถจำลองเป็นการเคลื่อนที่ผ่านกราฟที่มีต้นทุนไม่ติดลบได้ เช่น:

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

นอกจากนี้ยังเป็นตัวอย่างมาตรฐานของอัลกอริทึมแบบ greedy ที่ความถูกต้องขึ้นอยู่กับเงื่อนไขที่เฉพาะเจาะจง

ลองทำโจทย์ที่คล้ายกัน

วาดกราฟที่มีห้าโหนดและน้ำหนักขอบเป็นบวก จากนั้นลองใช้อัลกอริทึมของไดจ์คสตราด้วยมือพร้อมตารางระยะทาง ถ้าต้องการฝึกต่อ ลองสร้างกราฟใหม่ของคุณเองแล้วตรวจดูให้ชัดว่าแต่ละโหนดปลอดภัยที่จะปิดงานเมื่อใด