计算机仿真
計算機倣真
계산궤방진
COMPUTER SIMULATION
2013年
11期
352-355
,共4页
最短路径%狄杰斯特拉算法%标识矩阵%回溯法%所有最短路径
最短路徑%狄傑斯特拉算法%標識矩陣%迴溯法%所有最短路徑
최단로경%적걸사특랍산법%표식구진%회소법%소유최단로경
The shortest path%Dijkstra algorithm%Identity matrix%Backtracking algorithm%All of the shortest path
针对求有权图中任意两个顶点间的所有最短路径问题,提出了Dijkstra算法的改进.改进算法以加权图的邻接矩阵为基础,首先求出从一个顶点到其它各顶点的最短路径长度向量,然后由邻接矩阵和最短路径长度向量构造标识矩阵,最后用回溯法搜索标识矩阵得到从始点到其它各顶点的所有最短路径.改进算法具有使用范围广、计算规模小、计算过程简化、计算机易于实现等优点.改进算法的核心是用回溯法求解所有最短路径的运算,提出了从终点到始点的回溯求解问题,并且给出了求解任意两个顶点间的所有最短路径的快速算法.改进算法充分利用了标识矩阵所提供的路径信息经过回溯搜索得到两个顶点间的所有最短路径.仿真结果表明,改进算法对于求图中任意两个顶点间的所有最短路径行之有效.
針對求有權圖中任意兩箇頂點間的所有最短路徑問題,提齣瞭Dijkstra算法的改進.改進算法以加權圖的鄰接矩陣為基礎,首先求齣從一箇頂點到其它各頂點的最短路徑長度嚮量,然後由鄰接矩陣和最短路徑長度嚮量構造標識矩陣,最後用迴溯法搜索標識矩陣得到從始點到其它各頂點的所有最短路徑.改進算法具有使用範圍廣、計算規模小、計算過程簡化、計算機易于實現等優點.改進算法的覈心是用迴溯法求解所有最短路徑的運算,提齣瞭從終點到始點的迴溯求解問題,併且給齣瞭求解任意兩箇頂點間的所有最短路徑的快速算法.改進算法充分利用瞭標識矩陣所提供的路徑信息經過迴溯搜索得到兩箇頂點間的所有最短路徑.倣真結果錶明,改進算法對于求圖中任意兩箇頂點間的所有最短路徑行之有效.
침대구유권도중임의량개정점간적소유최단로경문제,제출료Dijkstra산법적개진.개진산법이가권도적린접구진위기출,수선구출종일개정점도기타각정점적최단로경장도향량,연후유린접구진화최단로경장도향량구조표식구진,최후용회소법수색표식구진득도종시점도기타각정점적소유최단로경.개진산법구유사용범위엄、계산규모소、계산과정간화、계산궤역우실현등우점.개진산법적핵심시용회소법구해소유최단로경적운산,제출료종종점도시점적회소구해문제,병차급출료구해임의량개정점간적소유최단로경적쾌속산법.개진산법충분이용료표식구진소제공적로경신식경과회소수색득도량개정점간적소유최단로경.방진결과표명,개진산법대우구도중임의량개정점간적소유최단로경행지유효.
