计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (10): 108-109.DOI: 10.3778/j.issn.1002-8331.2009.10.032

• 网络、通信、安全 • 上一篇    下一篇

互联网络RCP(n)的最短路算法

王 敏1,高太平1,2,刘宏英1,3,闫宇琦1   

  1. 1.山西大学 计算机与信息技术学院,太原 030006
    2.计算智能与中文信息处理省部共建教育部重点实验室,太原 030006
    3.山西大同大学 数学与计算机科学学院,山西 大同 037009
  • 收稿日期:2008-02-20 修回日期:2008-04-28 出版日期:2009-04-01 发布日期:2009-04-01
  • 通讯作者: 王 敏

Shortest path algorithm of RCP(n) networks

WANG Min1,GAO Tai-ping1,2,LIU Hong-ying1,3,YAN Yu-qi1   

  1. 1.School of Computer & Information Technology,Shanxi University,Taiyuan 030006,China
    2.Key Laboratory of Ministry of Education for Computation Intelligence & Chinese Information Processing,Taiyuan 030006,China
    3.School of Mathematics and Computer Science,Shanxi Datong University,Datong,Shanxi 037009,China
  • Received:2008-02-20 Revised:2008-04-28 Online:2009-04-01 Published:2009-04-01
  • Contact: WANG Min

摘要: RCP(n)是最近提出的一种新型互联网络拓扑结构,是由环、Petersen图和交叉立方体所组成的,具有短直径、良好的可扩展性和正则性以及较小的构造开销的性质,是一种具有良好拓扑性质的互联网络。针对RCP(n)上节点编码的特点,采用逐步分解编码,依次寻找路径的方法给出了寻找RCP(n)上任意两点间最短路的一个多项式算法,为RCP(n)上作进一步的路由算法、最优分组等通讯性能的研究提供了理论支持,因此具有一定的理论意义和应用价值。

Abstract: RCP(n) which has been proposed recently,consists of ring,Petersen graph and crossing cube.It has shorter diameter,regularity,good extensibility and lest construction costs,so it is a kind of interconnection network having good topological characteristics.This paper,by the codes’ characteristics of RCP(n),gives the polynomial shortest path algorithm of between discretionary two nodes in RCP(n) adopting disintegrating codes step by step and finding path in turn.This algorithm provides theory support for studying communication capabilities such as route algorithm,optimization grouping,so it has theory significance and application value.