Calculating Shortest Path on Edge-Based Data Structure of Graph
Guilin Chen, Mingyong Pang, Jidong Wang · 2007
In this paper, a versatile edge-centered data structure is presented based on an analysis about classical representations of graph or network topology. The data structure has many good properties of convenient data accessing, compact topological representation and intuitionistic graph operating, and so on. Further, the data structure has capabilities of representing various networks with arbitrary complexity and topology and implementing codes of various graph algorithms with easy and efficient way. Based on the data structure and the breadth-first traversal strategy, an algorithm is proposed and built for efficiently calculating the shortest path between an given vertex and each other vertex in even very large-scale graph. Experiments and results show that our data structure has the better performance about time and space. It can act as basic data structure in implementations of various graph algorithms and in related applications.