ในทฤษฎีกราฟ ต้นไม้วิถีสั้นสุด เป็นต้นไม้ที่ได้จากการแก้ปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียวบนกราฟที่กำหนดให้ โดยต้นไม้นี้จะเป็นกราฟย่อยของกราฟนั้นและระยะทางระหว่างรากกับจุดยอดใด ๆ มีค่าน้อยที่สุด การที่แก้ปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียวแล้วได้ต้นไม้นั้นเพราะว่าหากมีสองวิถีระหว่างรากกับโหนด v (มีวัฏจักร) เราสามารถเลือกใช้วิถีที่สั้นกว่า และลบเส้นเชื่อมที่มีระยะทางของวิถีที่ยาวกว่าได้โดยไม่ทำให้ระยะทางจากรากไปโหนดใดๆเพิ่มขึ้น หากโหนดทุกๆคู่ในกราฟที่กำหนดให้มีวิถีสั้นสุดเพียงแบบเดียว จะได้ว่าต้นไม้วิถีสั้นสุดก็จะมีเพียงแบบเดียวด้วยเช่นกัน ในกราฟที่ไม่มีน้ำหนักติดลบ ขั้นตอนวิธีของไดค์สตรา สามารถคำนวณหาต้นไม้วิถีสั้นสุดได้ สำหรับกราฟที่มีน้ำหนักติดลบ สามารถใช้ ขั้นตอนวิธีของเบลแมน-ฟอร์ด แทนได้ ดี.
สารบัญ
1 ความสัมพันธ์: ปัญหาวิถีสั้นสุด
วิถีสั้นสุดบนกราฟไม่ระบุทิศทางที่ไม่ถ่วงน้ำหนักระหว่างจุดยอด 6 กับ 1 คือ (6, 4, 5, 1) ในทฤษฎีกราฟ ปัญหาวิถีสั้นสุด (shortest path problem) เป็นปัญหาที่ต้องการหาวิถีสั้นสุดระหว่างจุดยอด 2 จุดภายในกราฟ กล่าวคือในวิถีสั้นสุดนั้น ผลรวมของน้ำหนักในเส้นเชื่อมแต่ละเส้นรวมกันแล้วน้อยที่สุดในบรรดาวิถีทั้งหมด ตัวอย่างปัญหานี้เช่นการหาวิธีเดินทางจากจุดหนึ่งไปอีกจุดหนึ่งในแผนที่ ในกรณีนี้ จุดยอดแทนด้วยสถานที่ต่างๆ ส่วนเส้นเชื่อมแทนด้วยถนนหรือเส้นทาง และน้ำหนักบนเส้นเชื่อมแทนด้วยเวลาในการเดินทางด้วยถนนหรือเส้นทางนั้น.
ดู ต้นไม้วิถีสั้นสุดและปัญหาวิถีสั้นสุด
