Abstract: The complex networking graph was studied to solve the shortest-path problem with definite track. The concept of direct/indirect adjacent edges was proposed which extended the concept of path to that of line and improved the storage of the adjacency matrix of the simple graph. The space storage structure was used to store the complex networking graph based on the concept of the direct/indirect adjacent edges. The shortest-path algorithm was designed, which used the public transportation search as the example. The theoretical analysis and experimental results show that this algorithm is better than Dijkstra algorithm in terms of time and space.

Key words: complex networking graph, definite track, direct adjacent edge, indirect adjacent edge, space storage structure, shortest-path algorithm

摘要： 以复杂网络图为研究对象，针对有确定轨迹的最短路径问题，提出直接/间接邻边的概念，将路径的概念引申为线路，改进简单图的邻接矩阵存储，采用空间存储结构存储基于直接/间接邻边概念的复杂网络图，并以公交查询问题为例设计了最短路径算法。算法分析及实验结果表明该算法的时空性能均优于Dijkstra算法。

关键词: 复杂网络图, 确定轨迹, 直接邻边, 间接邻边, 空间存储结构, 最短路径算法