中文摘要：

针对Theologou等给出的求解网络可靠度的factoring算法,分析该算法存在的冗余计算问题,给出DTN_OBDD算法。基于边排序策略的邻接终点矩阵方法,有效计算最小路集,将边失效特性引入网络可靠度分析中;基于最快路径求解公式,提高容量和时延约束下可行路径的筛选效率;构建所有可行路径的符号OBDD表示,遍历OBDD计算网络可靠度。以Python的igraph包生成的5组随机网络图为例,验证了DTN_OBDD算法的有效性,其中50个节点、201条边、状态空间为250的网络可靠度求解时间不超过80s。

英文摘要：

The redundant computations cannot be avoided in Theologou＇s factoring algorithm.To solve the problem,an OBDDbased algorithm DTN_OBDD was presented.The traditional adjacency matrix method was extended,which was used to enumerate minimal paths efficiently,to evaluate the reliability of a network with imperfect nodes and links based on edge ordering strategy.To enhance the computing efficiency,the quickest path problem was introduced to compute the feasible path.The network reliability was computed by traversing the OBDD which was constructed by all feasible paths.Five sets random networks were generated by Python＇s igraph library to validate the performance of the algorithm.Experimental results show the effectiveness of DTN_OBDD,it takes less than 80 sto calculate the reliability of the network with 50 nodes,201edges and 250 network states.