一种新的交叉立方体最短路径路由算法  

A Novel Shortest Path Routing Algorithm in the Crossed Cube

作　　者：喻昕[1] 吴敏[1] 王国军[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083

出　　处：《计算机学报》2007年第4期615-621,共7页Chinese Journal of Computers

基　　金：国家杰出青年科学基金(60425310);教育部青年教师奖励计划项目基金(教人[2002]5号)资助.

摘　　要：Efe提出的交叉立方体(crossed cube)是超立方体(hypercube)的一种变型.交叉立方体的某些性质优于超立方体,比如其直径几乎是超立方体的一半.Efe提出了时间复杂度为O(n2)的交叉立方体最短路径路由算法.Chang等人扩展了Efe的算法,时间复杂度为O(n),它在路由的每一步有更多条边作为最短路径可供寻路选择.但这些边并没有包含全部可进行最短路径路由的边.文中给出了结点各边可进行最短路径路由的充要条件,并在此基础上提出了一种时间复杂度为O(n2)的交叉立方体最短路径路由算法,它在路由的每一步都将所有的最短路径边作为候选边.理论分析和实例表明它可输出任意一条最短路径.The crossed cube proposed by Efe is a variation of hypercube, but some properties of the former are superior to those of the latter. For example, the diameter of the crossed cube is approximately half that of the hypercube. Efe presented a shortest path routing algorithm in the crossed cube, which has a time complexity of O（n^2）. Chang＇s algorithm that extends Efe＇s uses more candidate links at each routing step for the shortest path routing from source node to destination node. However, those links still do not contain all the links that belong to the shortest paths. This paper first introduces the sufficient and necessary conditions for each link of one node is a candidate link of a shortest path, and then proposes a shortest path routing algorithm capable of choosing one from all the candidate links that belong to shortest paths at each routing step. Its time complexity is O（n^2）. Theoretical analysis and case studies show that the algorithm can output any shortest path.

关 键 词：交叉立方体 超立方体 互联网络 最短路径 路由算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]