บทที่ 28 เส้นทางสั้นสุด
จบบทนี้ น้องจะหาเส้นทางที่ใช้เวลาหรือค่าใช้จ่ายน้อยที่สุดบนกราฟที่ถนนยาวไม่เท่ากันได้ ทั้งจากจุดเดียวด้วย Dijkstra แบบอาเรย์และแบบ priority_queue เมื่อมีน้ำหนักติดลบด้วย Bellman-Ford ซึ่งตรวจวงที่วนแล้วค่าใช้จ่ายลดลงไม่สิ้นสุดได้ด้วย และระหว่างทุกคู่ด้วย Floyd-Warshall จะพิมพ์เส้นทาง นับจำนวนทางที่สั้นที่สุด เริ่มจากหลายจุดพร้อมกัน และหาทางบนตารางที่แต่ละช่องมีค่าผ่าน โจทย์เส้นทางสั้นสุดออกในค่าย 2 และ TOI แทบทุกปี ส่วนใหญ่ไม่ได้ยากที่ตัววิธี แต่ยากที่การเลือกวิธีให้ตรงกับขอบเขต และไม่พลาดกับดักอย่างระยะเกิน int หรือคู่เก่าในคิว ซึ่งบทนี้วัดและทำให้พังให้เห็นทุกจุด
ในบทนี้
| หน้า | ได้อะไร |
|---|---|
| 28.1 BFS ไม่พอ และ Dijkstra แบบอาเรย์ | กราฟมีน้ำหนัก ตัวอย่างที่ BFS ตอบผิด การผ่อนระยะ ความคิดของ Dijkstra และแบบ O(V2) กับดัก INT_MAX ล้น |
| 28.2 Dijkstra ด้วย priority_queue | lazy deletion O((V + E) log V) วัดเวลาเทียบแบบอาเรย์ กับดักไม่ข้ามคู่เก่า ลืม greater และระยะเก็บใน int |
| 28.3 พิมพ์เส้นทาง นับทาง และตาราง | parent นับทางที่สั้นที่สุด หลายจุดเริ่ม ตารางที่ช่องมีค่าผ่าน และ BFS ที่ยอมเข้าคิวซ้ำ |
| 28.4 น้ำหนักติดลบและ Bellman-Ford | ตัวอย่างที่ Dijkstra ผิด Bellman-Ford O(VE) ตรวจวงติดลบและหาจุดที่ได้รับผลกระทบ |
| 28.5 Floyd-Warshall และการเลือกวิธี | ระยะทุกคู่ O(V3) ลำดับลูปที่ต้องถูก อนันต์ที่ไม่ล้น และตารางเลือกวิธีตามขอบเขต |