ต้นไม้วิถีสั้นสุด

ในทฤษฎีกราฟ ต้นไม้วิถีสั้นสุด เป็นต้นไม้ที่ได้จากการแก้ปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียวบนกราฟที่กำหนดให้ โดยต้นไม้นี้จะเป็นกราฟย่อยของกราฟนั้นและระยะทางระหว่างกับจุดยอดใด ๆ มีค่าน้อยที่สุด

การที่แก้ปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียวแล้วได้ต้นไม้นั้นเพราะว่าหากมีสองวิถีระหว่างรากกับโหนด v (มีวัฏจักร) เราสามารถเลือกใช้วิถีที่สั้นกว่า และลบเส้นเชื่อมที่มีระยะทางของวิถีที่ยาวกว่าได้โดยไม่ทำให้ระยะทางจากรากไปโหนดใดๆเพิ่มขึ้น

หากโหนดทุกๆคู่ในกราฟที่กำหนดให้มีวิถีสั้นสุดเพียงแบบเดียว จะได้ว่าต้นไม้วิถีสั้นสุดก็จะมีเพียงแบบเดียวด้วยเช่นกัน

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

อ้างอิง

Cahn, Robert S. Wide Area Network Design.

ดูเพิ่ม

• ปัญหาวิถีสั้นสุด