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

摘要

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

主权项

一种采用循环深度优先遍历的最长路预置保护P圈生成方法，其特征在于，所述方法是先根据通信网络拓扑结构，模拟出图G，求取图G中给定的两个相邻节点s、t间的最长路径r；在最长路径r上添加所述节点s、节点t间的直连边e，得到一条最长圈，即为所求的预置保护P圈；求节点s和节点t间的最长路径的步骤如下：2‑1)不考虑边s→t，以节点s为根进行深度优先遍历，求得节点s和节点t间的一条主路径r；2‑2)依次忽略主路径r中的每条边及除了该边节点以外的其它节点，以该边开始节点为根进行递归深度优先遍历，求得每条边的一条替换路径，并记该边为替换路径的忽略边，一起存入路径集Q；2‑3)在路径集Q中，依次取出最长路径r′，并删除路径集Q中对应的r′，并且判断所述路径r′中是否包含主路径r中的节点，如果不是，则调整主路径；2‑4)调整完成后新的主路径r即为相邻节点s和t间的最长路径。