作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2013, Vol. 39 ›› Issue (8): 142-146. doi: 10.3969/j.issn.1000-3428.2013.08.030

• 移动互联与通信技术 • 上一篇    下一篇

独立路径问题的算法设计

孙智帅,谢 政,陈 挚   

  1. (国防科学技术大学理学院,长沙 410073)
  • 收稿日期:2012-04-23 出版日期:2013-08-15 发布日期:2013-08-13
  • 作者简介:孙智帅(1987-),男,硕士研究生,主研方向:网络优化;谢 政,教授;陈 挚,副教授
  • 基金资助:
    国家部委基金资助项目

Algorithm Design for Disjoint Path Problem

SUN Zhi-shuai, XIE Zheng, CHEN Zhi   

  1. (Science School, National University of Defense Technology, Changsha 410073, China)
  • Received:2012-04-23 Online:2013-08-15 Published:2013-08-13

摘要: 根据网络中可供选择的路由数目,提出独立路径的一个新问题,即求网络中最多同时存在多少条相互独立的路径。同时,针对选择最优路由,研究求权值和最小的K(K>1, K为整数)条独立路径的问题,发现和证明独立路径与网络流的关系,并采用网络流方法设计简单算法。应用结果表明,该算法的复杂度较小,可用于解决网络通信中的多径路由问题。

关键词: 独立路径, 弧独立, 顶点独立, 多径路由, 网络流, 网络算法

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

中图分类号: