A Novel Shortest Path Routing Algorithm in the Crossed Cube
Guoyin Wang · Chinese Journal of Computers · 2007
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(n2).Chang et al′s algorithm that extends Efe 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(n2).Theoretical analysis and case studies show that the algorithm can output any shortest path.