摘要
传统Dijkstra算法是计算网络图单源最短路径的经典算法,但不适应于现实中存在的两区域交叉网络图。提出了新的区域特征码概念,设计了两区域交叉网络图的区域特征码和访问控制逻辑,并以此为基础改进了Dijkstra算法。实验证明,改进以后的Dijkstra算法能正确地计算两区域交叉网络图的单源最短路径,其时、空复杂度与原算法相同。通过这种改进,扩展了Dijkstra算法的适应范围。
The traditional Dijkstra algorithm is the classical algorithm to calculate the single-source shortest path for a network diagram,but not suited for two regional-cross network diagrams in reality.In this paper,the new concept of regional signature was put forward,and the regional signature and access-control logic for two regional-cross network diagram were designed too.Based on these,the Dijkstra algorithm was improved.The experiment proved that the improved Dijkstra algorithm can correctly calculate the single-source shortest path for two region-cross network diagrams,its place complexity &time complexity are the same as the traditional algorithm.Through this improvement,the adaptation range of the Dijkstra algorithm was expanded.
出处
《计算机科学》
CSCD
北大核心
2014年第S1期296-299,共4页
Computer Science
基金
湖南省教育科学重大项目(XJK011DDUT003)
湖南省科技计划项目(2012TZ2018
2013SK3137)
湖南第一师范学院项目(XYS10Z07
XYS11Z06)
计算机网络精品课程项目资助