摘要： 针对交换超立方网络的最短路由问题，提出一个交换超立方网中的最短路径路由算法。利用图论的方法，通过引进子网的概念，研究交换超立方网的拓扑性质，给出节点各边可进行最短路径路由的充要条件，得到其时间复杂度为 。理论分析和仿真结果表明，该算法可输出交换超立方网中任意两节点间的一条最短路径。

关键词: 交换超立方网, 相似子网, 最短路径, 路由算法, 同构, 映射

Abstract: Based on the problem of the shortest path between two nodes in the exchanged hypercube network, the method of the graph theory is employed to study the topological property of the exchanged hypercube network by introducing the concept of similare subnet, the sufficient and necessary conditions which guarantee some link of one node to become a candidate link of the shortest path, are presented. At the same time, a shortest path routing algorithm with time complexity on the exchanged hypercube network is obtained, the theoretical analysis and the simulation result show that above algorithm can output the shortest path between any two nodes in the exchanged hypercube network.

Key words: exchanged hypercube network, similar subnet, shortest path, routing algorithm, isomorphism, mapping

中图分类号: 

• TP393