两区域交叉网络图的Dijkstra改进算法

摘要：

传统Dijkstra算法是计算网络图单源最短路径的经典算法,但不适应于现实中存在的两区域交叉网络图.提出了新的区域特征码概念,设计了两区域交叉网络图的区域特征码和访问控制逻辑,并以此为基础改进了Dijkstra算法.实验证明,改进以后的Dijkstra算法能正确地计算两区域交叉网络图的单源最短路径,其时、空复杂度与原算法相同.通过这种改进,扩展了Dijkstra算法的适应范围.

关键词：Dijkstra算法、两区域交叉网络图、区域特征码、访问控制逻辑

所属期刊栏目：41

分类号：TP391(计算技术、计算机技术)

资助基金：湖南省教育科学重大项目XJK011DDUT003;湖南省科技计划项目2012TZ2018,2013SK3137;湖南第一师范学院项目XYS10Z07,XYS11Z06;计算机网络精品课程项目资助

在线出版日期：2014-08-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：296-299