数字通信
數字通信
수자통신
DIGIT L COMMLINIC TION
2011年
4期
72-73
,共2页
并行最短路径算法%Dijkstra算法%最短路径算法%路由算法
併行最短路徑算法%Dijkstra算法%最短路徑算法%路由算法
병행최단로경산법%Dijkstra산법%최단로경산법%로유산법
针对两点间最短路径问题,提出一种新的并行求解算法.该算法通过不断消去中间的节点和边以简化图的结构,以局部最优而达到全局最优.相对于经典的串行Dijkstra算法,天然地具有并行特性,对稀疏图更加有效,算法复杂度较低.仿真结果证明:该算法对于任意类型的无向图或有向图,总是可准确求得其最短路径.
針對兩點間最短路徑問題,提齣一種新的併行求解算法.該算法通過不斷消去中間的節點和邊以簡化圖的結構,以跼部最優而達到全跼最優.相對于經典的串行Dijkstra算法,天然地具有併行特性,對稀疏圖更加有效,算法複雜度較低.倣真結果證明:該算法對于任意類型的無嚮圖或有嚮圖,總是可準確求得其最短路徑.
침대량점간최단로경문제,제출일충신적병행구해산법.해산법통과불단소거중간적절점화변이간화도적결구,이국부최우이체도전국최우.상대우경전적천행Dijkstra산법,천연지구유병행특성,대희소도경가유효,산법복잡도교저.방진결과증명:해산법대우임의류형적무향도혹유향도,총시가준학구득기최단로경.
