การประยุกต์ใช้กราฟในชีวิตประจำวัน

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

เทคนิคการหาเส้นทางที่สั้นที่สุดเป็นเรื่องที่มีผู้สนใจเป็นจำนวนมาก มีผู้พัฒนาวิธีการหาเส้นทางสั้นที่สุดหลายวิธีการ อย่างไรก็ดีวิธีการต่าง เหล่านี้เป็นวิธีการทางคณิตศาสตร์

ตัวอย่าง

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

วิธีการแก้ปัญหา

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

เริ่มต้น
จากโหนด 4 และ 10 ที่ลากไปถึงปลายทางคือโหนด 5 จากนั้นหาทางต่อ
 
ทำการขยายโหนดต่อไป โดยหาทางที่ดีที่สุดได้ดังนี้
 
จุดปลายทางคือจุดต้นทางที่ปัญหากำหนด ซึ่งสามารภคำนวนหาระยะทางสั้นที่สุดได้ 14 มาจากเส้นทางโหนด 2
 
ระยะทางจากโหนด 1 ไปโหนด 2 โหนด 3 โหนด 4 และโหนด 5 เป็นเส้นทางที่สั้นที่สุด มีระยะทาง 14


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