樹路徑長度

如果葉結(jié)點(diǎn)是帶權(quán)的，路徑長度與權(quán)值的乘積稱該葉結(jié)點(diǎn)的“加權(quán)路徑長度”。所有葉結(jié)點(diǎn)的加權(quán)路徑長度之和稱“樹加權(quán)路徑長度”。

除葉結(jié)點(diǎn)外的所有結(jié)點(diǎn)的路徑長度之和稱“樹內(nèi)部路徑長度”。所有葉結(jié)點(diǎn)的路徑長度之和稱“樹外部路徑長度”。

路徑長度是最常用的路由度量標(biāo)準(zhǔn)。一些路由協(xié)議允許網(wǎng)管給每個網(wǎng)絡(luò)鏈接人工賦以代價值，這種情況下，路由

路由長度是所經(jīng)過各個鏈接的代價總和。其它路由協(xié)議定義了跳數(shù)，即分組在從源到目的的路途中必須經(jīng)過的網(wǎng)絡(luò)產(chǎn)品，如路由器的個數(shù)。

最短路徑樹Dijkstra算法

設(shè)置兩個定點(diǎn)的集合T和S，集合S中存放已找到最短路徑的定點(diǎn)，集合T中存放當(dāng)前還未找到的最短路徑的定點(diǎn)。初始狀態(tài)時，集合S中只包含源點(diǎn)v0然后不斷從集合T中選取到定點(diǎn)v0路徑長度最短的頂點(diǎn)u加入集合S，集合S中每加入一個新的頂點(diǎn)u，都要修改定點(diǎn)v0到集合T中剩余頂點(diǎn)的最短路徑長度值，集合T中每個頂點(diǎn)新的最短路徑長度值為原來的最短路徑長度值與定點(diǎn)u的最短路徑長度值加上u到該頂點(diǎn)的路徑長度值中的較小值。此過程不斷重復(fù)，直到集合T的頂點(diǎn)全部加入到集合S為止 。

最短路徑樹Floyd算法

從代表任意兩個節(jié)點(diǎn)

考慮一個連通無向圖

在一個所有最短路徑都明確（例如沒有負(fù)長度的環(huán)）的連通圖，我們可以使用如下算法構(gòu)造最短路徑樹：

使用Dijkstra算法或Floyd算法計(jì)算圖 G 從根節(jié)點(diǎn) v 到 頂點(diǎn) u 的最短距離

對于所有的非根頂點(diǎn)

用各個頂點(diǎn)和它們的父節(jié)點(diǎn)之間的邊構(gòu)造最短最短路徑樹。

上面的算法保證了最短路徑樹的存在。像最小生成樹一樣，最短路徑樹通常也不只有一個的。在所有邊的權(quán)重都相同的時候，最短路徑樹和廣度優(yōu)先搜索樹一致。在存在負(fù)長度的環(huán)時，從