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

Improved Dijkstra Algorithm for Two Regional-cross Network Diagram

传统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.