超立方体中过k个指定点的最短路径

作者：陈荷花

来源：山西师范大学学报(自然科学版), 2016, 30(02): 12-16.

DOI：10.16207/j.cnki.1009-4490.2016.02.003

• 超立方体
• 节点编码
• 指定点
• 最短路径

利用超立方体的拓扑结构,基于其内部节点编码的特点,分析研究得到在n维超立方体Qn中任意两节点s、t之间经过k(k<n)个指定点的最短路径算法.该算法共包括了十个步骤,在最坏的情况下执行2n2+2n(n2+2)次运算,算法的时间复杂度为O(n3),属于多项式计算.

• 单位
  太原学院