An algorithm for single source shortest path in networks using depth first search

摘要：

This paper presents an efficient algorithm for finding the single source shortest path in the complex networks and graphs, which respectively label the nodes with their current shortest distance to the source in depth first search. Meanwhile,through experiments on matrix-represented networks of different sizes (from 182 nodes to 13770 nodes), we found it has a satisfactory average time complexity of O(kV) (k＜18, V=n-o, nmeans the number of nodes and o is the number of obstacles).We also present an analysis of time complexity, showing it as an intelligent algorithm with more practical and prospective value.

关键词： depth first search single source shortest path labeling, network

作者: ZHUANG Ming YANG Xiao

作者单位: College of Mathematics,Physics and Information Engineering, Zhejiang normal University zhejiang Jinh Department of Electrical Engineering, Rutgers university N J, 0854, US

会议类型: 国际会议

会议名称: 第二届国际计算机新科技与教育学术会议(Proceedings of the Second International Conference on Computer Science & Education ICCSE2007)

会议地点: 武汉

会议语种:英文

页码: 322-326

在线出版日期: 2007-07-25（万方平台首次上网日期，不代表论文的发表时间）