Algorithm for Single Source Shortest Path in Networks Using Depth First Search
Zhuang Ming · Journal of Chinese Computer Systems · 2008
For the first time, this paper proposes an efficient algorithm for single source shortest path in complex networks and graphs, by labeling the nodes with its current shortest distance from the source in depth first search. Further more, through experiments on matrix-represented networks of different sizes (from 182 nodes to 13770 nodes), we found it has a satisfactory time complexity of O(kV) (k18, V=n-o, n means the number of nodes, o means the number of obstacles). we also present a analysis of time complexity. An intelligent algorithm with more practical and prospective value are reported.