A Novel Shortest Path Approach for Multiple Layers of Graphs
Zhiyuan Jerry Lin, Yan Li · 2009
Multiple layers in graphs or vector maps are a general case but complicated network in various applications. The classical shortest path algorithm, such as the Dijkstra's algorithm, can not be applied to the multiple layers directly. A new shortest path approach for multiple layers of graphs or vector maps was proposed in this paper. Firstly, the multiple layers should be overlaid with an improved algorithm based on scan-line and rebuild the topological relationship. And then, an improved algorithm for the shortest path with heap was advanced and analyzed the complexity. Through a theoretical reasoning, the calculating complexity is reduced from O(n2) to O((n+k)log(n+k)), where n is the number of vertices and k is the number of points of intersection. Finally, a novel approach of calculating shortest path was excogitated to the multiple layers in the complexity network analysis. After correlative experiment, the result indicates that this novel approach can be effectively applied to the shortest path calculation for the multiple layers of graphs or vector maps.