计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2011年
25期
71-73,136
,共4页
最短路径树%算法%动态更新%扩展最短路径树
最短路徑樹%算法%動態更新%擴展最短路徑樹
최단로경수%산법%동태경신%확전최단로경수
动态SPT算法是在图的拓扑改变时,以原有SPT为基础作局部更新;SPT动态更新需要解决寻找因为该改变而需要修正最短路径的相关节点的问题.对于传统的SPT定义先扩展,使节点记录距离相等的一条或多条最短路径,称之为ESPT.提出了一种不需记录后继的ESPT动态更新算法并加以证明,通过证明还说明在ESPT定义下该算法找到的所有节点都是动态更新所必要且充分的.给出算例,列出操作过程,对不同复杂度的图进行计算实验,将其结果与经典静态算法进行了对比.
動態SPT算法是在圖的拓撲改變時,以原有SPT為基礎作跼部更新;SPT動態更新需要解決尋找因為該改變而需要脩正最短路徑的相關節點的問題.對于傳統的SPT定義先擴展,使節點記錄距離相等的一條或多條最短路徑,稱之為ESPT.提齣瞭一種不需記錄後繼的ESPT動態更新算法併加以證明,通過證明還說明在ESPT定義下該算法找到的所有節點都是動態更新所必要且充分的.給齣算例,列齣操作過程,對不同複雜度的圖進行計算實驗,將其結果與經典靜態算法進行瞭對比.
동태SPT산법시재도적탁복개변시,이원유SPT위기출작국부경신;SPT동태경신수요해결심조인위해개변이수요수정최단로경적상관절점적문제.대우전통적SPT정의선확전,사절점기록거리상등적일조혹다조최단로경,칭지위ESPT.제출료일충불수기록후계적ESPT동태경신산법병가이증명,통과증명환설명재ESPT정의하해산법조도적소유절점도시동태경신소필요차충분적.급출산례,렬출조작과정,대불동복잡도적도진행계산실험,장기결과여경전정태산법진행료대비.
