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

陳荷花，高太平

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

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

陳荷花1，高太平2

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

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

超立方體；節點編碼；最短路徑

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

1 相關概念

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

圖1 四維超立方體Q4

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

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

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

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

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

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

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

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

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

2.1 算法思想

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

2.2 算法框圖

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

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

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，轉②；否則，進入下一步.

④記錄i=jk,si=sjk

.

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

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

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

⑧ 輸出：Ph=v0v1…vh，算法結束.

2.4 算法復雜度分析

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

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

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

3 實例驗證

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

圖3 四維超立方體Q4

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

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

4 結束語

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

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

[2]霍紅衛,莊心谷.超立方體上所有點對之間的最短路徑[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-),女,講師,碩士研究生,研究方向為圖論及網絡優化

時間：2014-05-16 11:32

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