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

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

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

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

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

 อ้างอิง 

 ดูเพิ่ม 
 ปัญหาวิถีสั้นสุด

หมวดหมู่:ทฤษฎีกราฟ
หมวดหมู่:บทความเกี่ยวกับ คณิตศาสตร์ ที่ยังไม่สมบูรณ์