Use Critical Sub-graph to Optimize the In-building Shortest Path Algorithm

The intelligentize and complication of buildings has fostered an interest in navigation inside buildings. This paper presents algorithm for shortest path searching inside building based on critical sub-graph. By the feature that some vertices of the in-building path graph are crucial for shortest path searching, the paper gives the definitions of the critical vertex and critical sub-graph and proposes a critical sub-graph based shortest path searching algorithm. The proposed algorithm skips over unimportant vertices so that the search space is greatly narrowed. The performance of the proposed algorithm is better optimized in contrast to the corresponding algorithms based on the whole path graph. The efficiency of the proposed algorithm has been confirmed by the experiments on real-world in-building path graph.