最短路徑樹

最短路徑樹（Shortest Path Tree, SPT）是一種用來解決最短路徑問題的數據結構。在圖論中，最短路徑問題是指給定一個圖和兩個頂點，找到連接這兩個頂點的權值最小的路徑。最短路徑樹就是將圖中的一個頂點作為根，生成一棵樹，使得從根到圖中其他每個頂點的路徑都是最短的。

最短路徑樹可以用迪傑斯特拉算法（Dijkstra's algorithm）來生成。迪傑斯特拉算法是一種用來找到圖中兩個頂點之間最短路徑的算法。該算法可以從圖中的一個頂點開始，逐步擴展到其他頂點，找到從起始頂點到圖中每個頂點的最短路徑。

最短路徑樹的應用非常廣泛，例如在交通網絡中，可以找到從一個城市到其他城市的最短路徑；在通信網絡中，可以找到數據傳輸的最優路徑；在生物學中，可以用來分析蛋白質互作用網絡等。