陳荷花，高太平

（1.太原大學外語師范學院，山西太原030012；2.山西大學計算機與信息技術(shù)學院，山西太原030006）

基于超立方體Qn節(jié)點編碼的最短路徑

陳荷花1，高太平2

（1.太原大學外語師范學院，山西太原030012；2.山西大學計算機與信息技術(shù)學院，山西太原030006）

基于超立方體節(jié)點編碼的特點，得到求任意兩節(jié)點間的一條最短路徑算法.算法包括八步驟，在最壞的情況下需要執(zhí)行n+2n2次運算，其時間計算復(fù)雜度為O(n2)，屬于多項式算法.

超立方體；節(jié)點編碼；最短路徑

超立方體（Hypercube）是互連網(wǎng)絡(luò)領(lǐng)域里最早提出的網(wǎng)絡(luò)拓撲結(jié)構(gòu)之一.最短路徑問題（簡稱SP）是圖論中研究的一個典型課題，求最短路徑的一個著名算法是Dijkstra算法[1]，它可以求出圖中從一個頂點到其它各頂點的最短路徑的長度及其一條最短路徑，其算法復(fù)雜度與網(wǎng)絡(luò)的節(jié)點規(guī)模同階.對于超立方體這種特殊的互連網(wǎng)絡(luò)，由于它的節(jié)點數(shù)是2n個，因此將Dijkstra算法用于超立方體會得到與2n同階的算法復(fù)雜度.本文就系統(tǒng)正常情況下，針對超立方體Qn節(jié)點編碼的特點，給出從始點s到終點t的一條最短路算法，這將為設(shè)計該網(wǎng)絡(luò)中的路由和容錯提供一定的理論基礎(chǔ).

1 相關(guān)概念

n維超立方體互連網(wǎng)絡(luò)Qn是一個簡單無向圖，Qn中任一節(jié)點a記為a=(a1a2…an),任一Qn由2n個節(jié)點和n2n-1條邊構(gòu)成.對Qn中節(jié)點依次從(00…0)到(11…1)進行n位二進制串xn-1xn-2…x0編碼，節(jié)點間的連接規(guī)則為：當且僅當其中兩個節(jié)點的二進制串恰有一位不同時，兩節(jié)點相連.圖1給出了一個4維超立方體互連網(wǎng)絡(luò)Q4拓撲結(jié)構(gòu)及其節(jié)點的編碼（從0000到1111），圖中有24=16個節(jié)點和4×24-1=32條邊.

圖1 四維超立方體Q4

為討論方便，文中新給出以下定義，未定義的記號和術(shù)語參見文獻[1].

定義1記Qn中與節(jié)點a的第j個分量互補的點為

定義2記Qn中節(jié)點s與節(jié)點t的分量中不相同的位為s和t的不同位.

定義3超立方體Qn中節(jié)點s與節(jié)點t的前k個不同位互補的點記作，其中*代表節(jié)點vk與s的相同位.

定義4超立方體Qn中節(jié)點s=(s1s2…sn)和t=（t1t2…tn）之間的漢明距離定義為：

當節(jié)點s與節(jié)點t的漢明距離為h時，它們的分量中會存在h個不同位，記vh=s(?sj1?sj2?…?sjh?)，其中sj1、sj2、…、sjh就是s與t不相同的h個分量.

在n維超立方體Qn中，兩節(jié)點s、t相鄰，當且僅當dH(s,t)=1.

定義5記Qn中過節(jié)點v1,v2,…,vk的一條路徑記作P=v1v2…vk.

2 基于超立方體Qn節(jié)點編碼的最短路算法

2.1 算法思想

首先計算出始點s到達終點t之間的漢明距離，記為h，即dH(s,t)=h，同時得知節(jié)點s、t的分量中存在h個不同位.然后改h個不同位中的最高位為其互補位，得到所求路徑上繼始點s后的第一個節(jié)點v1，隨后改h個不同位中的次高位為其互補位，得到所求路徑上繼節(jié)點v1后的又一個節(jié)點v2，依次下去，便可得到超立方體Qn中從始點s到達終點t的一條最短路徑.

2.2 算法框圖

在超立方體Qn中，有了從始點s到達終點t的一條最短路徑的算法思想后，為了更清晰地表達系統(tǒng)各環(huán)節(jié)之間的關(guān)系，給出本算法的流程圖，如圖2所示.

圖2 Qn中兩節(jié)點之間的一條最短路算法

2.3 算法步驟

算 法 ：輸 入 始 點s=(s1s2...sn),終點t=(t1t2...tn),置i=1,k=1.

①計算漢明距離dH(s,t)=h.

②取始點s和終點t各分量中的第i個相同分量si,ti.

③若si=ti,置i=:i+1，轉(zhuǎn)②；否則，進入下一步.

④記錄i=jk,si=sjk

.

⑤若i＜n,置i=:i+1，轉(zhuǎn)②；否則，進入下一步.

⑥記錄vk=s(?-sj1?-sj2?…?-sjk?)，v0=s，Pk=v0v1…vk.

⑦若k＜h，置i=:jk+1，k=:k+1，轉(zhuǎn)②；否則，進入下一步.

⑧ 輸出：Ph=v0v1…vh，算法結(jié)束.

2.4 算法復(fù)雜度分析

本文所做的算法復(fù)雜度分析主要是指時間復(fù)雜度分析.欲準確計算一個算法的時間復(fù)雜度，不僅需要對算法的程序進行一步一步分析，而且要考慮系統(tǒng)編譯的時間，可實際上對結(jié)果的意義不大.因此，具體操作中通常采用時間復(fù)雜度的漸進表示法，借用程序執(zhí)行步驟數(shù)的數(shù)量級來說明算法執(zhí)行效率的高低.

算法共有八個步驟.執(zhí)行步驟①需要n次比較，步驟③最多循環(huán)n次，最壞的情況下步驟⑤⑦各循環(huán)n次，記錄n次，即③～⑦需要2n2次計算.這樣，該算法在最壞的情況下最多需要執(zhí)行n+2n2次運算，因此本算法的計算復(fù)雜度為O(n2)，屬于多項式算法.

顯然，本算法的復(fù)雜度要比Dijkstra算法的復(fù)雜度O(2n)低很多，而且解決具體問題的針對性更強.

3 實例驗證

例1：在圖3所給4維超立方體Q4中，求出從始點s=(0000)到終點t=(1111)的一條最短路徑和從始點x=(0001)到終點y=(1110)的一條最短路徑.

圖3 四維超立方體Q4

解：依算法得，從始點s到終點t的一條最短路徑為：

從始點x到終點y的一條最短路徑為：

4 結(jié)束語

最短路問題是網(wǎng)絡(luò)中的一個經(jīng)典問題，本文針對Dijkstra算法在求最短路徑時的復(fù)雜性，討論研究了超立方體這一特殊的互連網(wǎng)絡(luò)結(jié)構(gòu)中，任意兩點間的最短路徑算法.文中基于超立方體Qn的節(jié)點編碼特點，提出了一種新的求最短路徑的算法.該算法屬于多項式算法，計算復(fù)雜度為O(n2)，克服了Dijkstra算法的不足之處.論文下一步的工作可以繼續(xù)探索超立方體互連網(wǎng)絡(luò)中，某些特定條件下，兩節(jié)點之間的最短路徑算法.當然，這些算法為設(shè)計該網(wǎng)絡(luò)中的路由和容錯提供了重要的理論支撐.

[1]J.A.邦迪,U.S.R.默蒂.圖論及其應(yīng)用[M].北京:科學出版社, 1984.

[2]霍紅衛(wèi),莊心谷.超立方體上所有點對之間的最短路徑[J].計算機學報,1996,19(2):154-157.

[3]徐鳳生.求最短路徑的新算法[J].計算機工程與科學,2006,28(2): 83-85.

[4]Saad Y,Schultz M H.Topological properties of hypercube[J].IEEE Transactions on Computers,1998,37(7):867-872.

[5]Tzeng N F,Wei S Z.Enhanced hypercube[J].IEEE Trans on Computers,1991,40(3):284-294.

【編校：許潔】

Shortest Path in Hypercube Based on Node Codes

CHEN Hehua1,GAO Taiping2
(1.Foreign Language Normal College,Taiyuan University,Taiyuan,Shanxi 030012,China;2.School of Computer and Information Technology,Shanxi University,Taiyuan,Shanxi 030006,China)

Based on the characteristic of the node codes in the n-dimensional hypercube,the shortest path algorithm between any two nodes was got.This algorithm involves eight steps.n+2n2times calculation should be executed in the worst case,and the algorithm complexity isO(n2).It belongs to a polynomial algorithm.

hypercube;node code;shortest path

TP301.6

A

1671-5365(2014)06-0092-02

2014-04-11修回：2014-05-05

國家自然科學基金項目(60803034)

陳荷花(1983-),女,講師,碩士研究生,研究方向為圖論及網(wǎng)絡(luò)優(yōu)化

時間：2014-05-16 11:32

http://www.cnki.net/kcms/detail/51.1630.Z.20140516.1132.009.html