摘要： 提出了在搜索过程中采用标记最短距离,调用递归函数用回溯搜索法求解网络最短距离的算法。该算法可以方便地求解复杂网络或复杂迷宫的通道与最短距离问题,在求解结果中给出从起点到网络通道上任意点的路径标识和最短距离值等信息,在无向加权图的最短路径求解中,显示出比Dijkstra方法小的时间复杂度。该算法克服了传统回溯法求解复杂迷宫时被时间复杂度和空间复杂度困扰的难题,显示出良好的应用前景。

关键词: 网络, 最短距离, 递归算法, 无向加权图

Abstract: An algorithm is presented for solving the shortest path in network by labeling the distance between start point and current exploring point with recursive backtracking maze search. The algorithm is very well suit to solving the shortest path problem in complex network or in complex maze, and gives an interested solution which contains information such as route label and the shortest path between start point and any connected point, and shows less time complexity when applied to solve an undirected weighted graph than Dijkstra’ algorithm did, and may be a breakthrough for time complexity and space complexity in solving maze by traditional algorithm.

中图分类号: 

• TP301.6