การหาเส้นทางสั้นที่สุด (Shortest Path Problems)

ตัวอย่าง

ต้องการหาทางเดินที่สิ้นที่สุดระหว่างโหนด 1 กับ โหนด 5

ในการแก้ปัญหามีหลายวิธี แต่วิธีหนึ่ง เราเริ่มจากจุดปลายทาง โดยทำให้เหมือนเป็นจุดต้นทาง และหาทางย้อนกลับมาที่จุดต้นทางโดยใช้ (x,y)

x  หมายถึง  เส้นทางโหนดจากจุดปลายทางมาถึงจุดนั้น
y  หมายถึง  ระยะทางจากจุดปลายทางผ่านเส้นทางมาทาง X

เริ่มต้น

จากโหนด 4 และ 10 ที่ลากไปถึงปลายทางคือโหนด 5 จากนั้นหาทางต่อ

ทำการขยายโหนดต่อไป โดยหาทางที่ดีที่สุดได้ดังนี้

จุดปลายทางคือจุดต้นทางที่ปัญหากำหนด ซึ่งสามารภคำนวนหาระยะทางสั้นที่สุดได้ 14 มาจากเส้นทางโหนด 2

ระยะทางจากโหนด 1 ไปโหนด 2 โหนด 3 โหนด 4 และโหนด 5 เป็นเส้นทางที่สั้นที่สุด มีระยะทาง 14

---

ที่มา : รศ. ยืน ภู่วรวรรณ, สำนักบริการคอมพิวเตอร์ มหาวิทยาลัยเกษตรศาสตร์