现代电子技术
現代電子技術
현대전자기술
MODERN ELECTRONICS TECHNIQUE
2008年
21期
188-191
,共4页
高速公路网%拓扑结构%Dijkstra算法%优化
高速公路網%拓撲結構%Dijkstra算法%優化
고속공로망%탁복결구%Dijkstra산법%우화
当高速公路网中出现交通事件时,其拓扑结构发生了变化,需要搜索新的最短路径并告知司机.由于信息发布具有较高的实时性,最短路径的搜索效率对高速公路信息服务的效率有重要影响.论文采用Dijkstra算法搜索高速公路网中的最短路径,并结合高速公路网的特点,用链结构将表示各收费站的点连接起来,简化了高速公路网的拓扑结构,从而大幅减少Dijkstra算法中的节点数.对算法的复杂度分析表明,这种方法大幅减少了路径搜索的复杂度,从而缩短了计算时间,提高了最短路径搜索效率.
噹高速公路網中齣現交通事件時,其拓撲結構髮生瞭變化,需要搜索新的最短路徑併告知司機.由于信息髮佈具有較高的實時性,最短路徑的搜索效率對高速公路信息服務的效率有重要影響.論文採用Dijkstra算法搜索高速公路網中的最短路徑,併結閤高速公路網的特點,用鏈結構將錶示各收費站的點連接起來,簡化瞭高速公路網的拓撲結構,從而大幅減少Dijkstra算法中的節點數.對算法的複雜度分析錶明,這種方法大幅減少瞭路徑搜索的複雜度,從而縮短瞭計算時間,提高瞭最短路徑搜索效率.
당고속공로망중출현교통사건시,기탁복결구발생료변화,수요수색신적최단로경병고지사궤.유우신식발포구유교고적실시성,최단로경적수색효솔대고속공로신식복무적효솔유중요영향.논문채용Dijkstra산법수색고속공로망중적최단로경,병결합고속공로망적특점,용련결구장표시각수비참적점련접기래,간화료고속공로망적탁복결구,종이대폭감소Dijkstra산법중적절점수.대산법적복잡도분석표명,저충방법대폭감소료로경수색적복잡도,종이축단료계산시간,제고료최단로경수색효솔.
