采用循环深度优先遍历的最长路预置保护P圈生成方法

摘要

本发明提供一种采用循环深度优先遍历的最长路预置保护P圈生成方法，是先模拟出通信网络的拓扑图，在拓扑图中求给定两个相邻节点，如节点s和节点t间的最长路径r；在最长路径r上添加所述节点s和节点t间的直连边e，得到一条最长圈，即为所求的预置保护P圈。本发明首次将近似hamiton回路的简化方法应用于P圈搜索，得到了最长路径问题的多项式复杂度，提高了效率，可应用于大规模通信网络。