ในทางคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์ต้นไม้เส้นทางที่สั้นที่สุดซึ่งมีรากอยู่ที่จุดยอดvของกราฟแบบไม่มีทิศทางและเชื่อมต่อกันGคือต้นไม้แผ่คลุมTของGโดยที่ระยะทางของเส้นทางจากรากvไปยังจุดยอดอื่นใดuในTคือ ระยะ ทาง ของเส้นทางที่สั้นที่สุดจากvไปยังuในG

ในกราฟที่เชื่อมต่อกันซึ่งมีเส้นทางที่สั้นที่สุดกำหนดไว้อย่างชัดเจน (เช่น ไม่มีวงจรที่มีความยาวติดลบ) เราสามารถสร้างต้นไม้เส้นทางที่สั้นที่สุดได้โดยใช้อัลกอริทึมต่อไปนี้:

1. คำนวณ dist( u ) ซึ่งเป็นระยะทางเส้นทางที่สั้นที่สุดจากรากvไปยังจุดยอดuในGโดยใช้อัลกอริทึมของ Dijkstraหรือ อัลกอริทึม ของBellman–Ford
2. สำหรับจุดยอดที่ไม่ใช่จุดรากu ทั้งหมด เราสามารถกำหนดจุดยอดแม่p _u ให้กับ u ได้ โดยที่p _uเชื่อมต่อกับuและ dist( p _u ) + edge_dist( p _u , u ) = dist( u ) ในกรณีที่มีตัวเลือกp _u หลายตัว ให้เลือกp _uที่มีเส้นทางที่สั้นที่สุดจากvไปยังp _uโดยมีจำนวนขอบน้อยที่สุด กฎการตัดสินกรณีที่มีค่าเท่ากันนี้จำเป็นเพื่อป้องกันการเกิดวงวนเมื่อมีวงจรที่มีความยาวเป็นศูนย์
3. สร้างแผนผังเส้นทางที่สั้นที่สุดโดยใช้เส้นเชื่อมระหว่างแต่ละโหนดกับโหนดแม่ของมัน

อัลกอริทึมข้างต้นรับประกันการมีอยู่ของต้นไม้เส้นทางที่สั้นที่สุด เช่นเดียวกับต้นไม้แผ่คลุมขั้นต่ำต้นไม้เส้นทางที่สั้นที่สุดโดยทั่วไปไม่ได้มีเพียงหนึ่งเดียว

ในกราฟที่น้ำหนักของขอบทุกเส้นเท่ากัน ต้นไม้เส้นทางที่สั้นที่สุดจะตรงกับต้นไม้ การค้นหาแบบกว้าง (Breadth-First Search Tree)

ในกราฟที่มีวงจรลบ ชุดของเส้นทางแบบง่ายที่สั้นที่สุดจากจุด vไปยังจุดยอดอื่นๆ ทั้งหมด ไม่จำเป็นต้องก่อตัวเป็นต้นไม้เสมอไป

สำหรับกราฟที่เชื่อมต่อกันอย่างง่าย สามารถใช้ต้นไม้เส้นทางที่สั้นที่สุด^{[ 1 ]}เพื่อแนะนำความสัมพันธ์ที่ไม่เป็นเชิงเส้นระหว่างการวัดความสำคัญของ เครือข่ายสองแบบ คือความใกล้ชิดและระดับโดยการสมมติว่ากิ่งของต้นไม้เส้นทางที่สั้นที่สุดมีความคล้ายคลึงกันทางสถิติสำหรับโหนดรากใด ๆ ในเครือข่ายหนึ่ง เราอาจแสดงให้เห็นว่าขนาดของกิ่งขึ้นอยู่กับจำนวนกิ่งที่เชื่อมต่อกับจุดยอดรากเท่านั้น กล่าวคือ ขึ้นอยู่กับระดับของโหนดราก จากนี้เราสามารถสรุปได้ว่าค่าผกผันของความใกล้ชิด ซึ่งเป็นมาตราส่วนความยาวที่เกี่ยวข้องกับแต่ละจุดยอด จะแปรผันเชิงเส้นโดยประมาณกับลอการิทึมของระดับ ความสัมพันธ์นี้ไม่แม่นยำนัก แต่สามารถจับความสัมพันธ์ระหว่างความใกล้ชิดและระดับในเครือข่ายจำนวนมากที่สร้างขึ้นจากข้อมูลจริง^{[ 1 ]}และความสำเร็จนี้ชี้ให้เห็นว่าต้นไม้เส้นทางที่สั้นที่สุดสามารถเป็นค่าประมาณที่มีประโยชน์ในการวิเคราะห์เครือข่าย

• ปัญหาเส้นทางที่สั้นที่สุด

Cahn, Robert S. (1998). การออกแบบเครือข่ายบริเวณกว้าง: แนวคิดและเครื่องมือเพื่อการเพิ่มประสิทธิภาพ . เครือข่าย. Morgan Kaufmann. ISBN 978-1558604582.

บทความเกี่ยวกับทฤษฎีกราฟนี้ ยัง ไม่สมบูรณ์คุณสามารถช่วยวิกิพีเดียได้โดยการเพิ่มข้อมูลที่ขาดหายไป

• วี
• ที
• อี