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

陳荷花，高太平

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

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

陳荷花1，高太平2

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

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

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

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

1 相關(guān)概念

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

圖1 四維超立方體Q4

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

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

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

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

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

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

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

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

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

2.1 算法思想

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

2.2 算法框圖

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

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

2.3 算法步驟

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

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

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

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

④記錄i=jk,si=sjk

.

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

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

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

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

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

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

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

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

3 實(shí)例驗證

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

圖3 四維超立方體Q4

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

從始點(diǎn)x到終點(diǎn)y的一條最短路徑為：

4 結(jié)束語

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

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

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

[3]徐鳳生.求最短路徑的新算法[J].計算機(jī)工程與科學(xué),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

國家自然科學(xué)基金項目(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