目的驅(qū)動最短路徑樹的快速算法

通過分析目的驅(qū)動最短路徑生成樹算法DDSP(Destination-driven Shortest Path) 的節(jié)點(diǎn)搜索過程，提出一種以較小的存儲空間為代價，減少DDSP 算法在搜索當(dāng)前節(jié)點(diǎn)、父節(jié)點(diǎn)和待處理節(jié)點(diǎn)時搜索空間的快速算法FDDSP( Fast destination-driven shortest path)。隨機(jī)網(wǎng)絡(luò)模型的仿真結(jié)果表明，F(xiàn)DDSP 算法生成的多播樹與DDSP 算法相同，但FDDSP 算法的效率更高。
關(guān)鍵詞：多播樹 最短路徑樹 最小生成樹 DDSP

AAbstract: Based on the low-cost shortest path tree(LSPT) algorithm DDSP(Destination-driven Short -est Path and through reducing it’s search space while searching current node,father node and rema -inder nodes ,we gain a FDDSP (Fast Destination-driven Shortest Path) algorithm that has high computing efciency paying out a few srorage space.The simulation result shows that the broadcast tree coming from FDDSP as same as the tree coming from DDSP,othermore,FDDSP is more effect -ive.
Key words: broadcast tree; shortest path tree; minimum spanning tree; DDSP(Destination-driven sho -rtest parh)