Abstract:
For finding the number of alternative routings in the network, this paper presents a new question of disjoint path, that is how to find the largest number of disjoint paths which exist at the same time in the network. And aiming at selecting the optimal route, consider the problem of getting K(K is an integer and K>1) disjoint paths, whose total weights are least. In addition, find the relation between the disjoint paths and the network flow and prove it. Benefiting from the network flow, a simple algorithm is designed. The results of application show that, the algorithm’s complexity is small. The algorithm can be used to solve the problem of multi-path routing in network communication.
Key words:
disjoint path,
arc disjoint,
vertex disjoint,
multi-path routing,
network flow,
network algorithm
摘要: 根据网络中可供选择的路由数目,提出独立路径的一个新问题,即求网络中最多同时存在多少条相互独立的路径。同时,针对选择最优路由,研究求权值和最小的K(K>1, K为整数)条独立路径的问题,发现和证明独立路径与网络流的关系,并采用网络流方法设计简单算法。应用结果表明,该算法的复杂度较小,可用于解决网络通信中的多径路由问题。
关键词:
独立路径,
弧独立,
顶点独立,
多径路由,
网络流,
网络算法
CLC Number:
SUN Zhi-Shuai, XIE Zheng, CHEN Zhi. Algorithm Design for Disjoint Path Problem[J]. Computer Engineering, 2013, 39(8): 142-146.
孙智帅, 谢政, 陈挚. 独立路径问题的算法设计[J]. 计算机工程, 2013, 39(8): 142-146.