软件导刊
軟件導刊
연건도간
SOFT WARE GUIDE
2010年
9期
68-69
,共2页
最短路径%定界%活节点
最短路徑%定界%活節點
최단로경%정계%활절점
以邻接矩阵为出发点,并根据邻接矩阵运算得到的可达矩阵判断是否存在从源点到目标点通路,然后从可达矩阵出发进行最短路径的搜索,这样的好处是减少了无效的搜索,从而减少了搜索时间;同时,以深度搜索优先首先找到一条通路,采用每次新加边长为可加边长中最短的原则,采用了新的定界手段,使用这些手段可以删除更多的活节点,从而减少算法计算量.结合这几个要点提出了一种新的最短路径算法.
以鄰接矩陣為齣髮點,併根據鄰接矩陣運算得到的可達矩陣判斷是否存在從源點到目標點通路,然後從可達矩陣齣髮進行最短路徑的搜索,這樣的好處是減少瞭無效的搜索,從而減少瞭搜索時間;同時,以深度搜索優先首先找到一條通路,採用每次新加邊長為可加邊長中最短的原則,採用瞭新的定界手段,使用這些手段可以刪除更多的活節點,從而減少算法計算量.結閤這幾箇要點提齣瞭一種新的最短路徑算法.
이린접구진위출발점,병근거린접구진운산득도적가체구진판단시부존재종원점도목표점통로,연후종가체구진출발진행최단로경적수색,저양적호처시감소료무효적수색,종이감소료수색시간;동시,이심도수색우선수선조도일조통로,채용매차신가변장위가가변장중최단적원칙,채용료신적정계수단,사용저사수단가이산제경다적활절점,종이감소산법계산량.결합저궤개요점제출료일충신적최단로경산법.