在目前的超大型積體電路（VLSI）的技術下，已經有辦法建構一個數千個處理器（processor）的大型平行及分散式系統（parallel and distributed system），例如Connection Machine [2]包含216個處理器。設計一個大型的平行及分散式系統一個蠻重要的步驟便是它的連結網路（interconnection network）的拓樸結構（topology），因為系統的效能往往受到網路的拓樸結構所影響。

蝴蝶圖（butterfly graph）原來被設計於架構在FFT網路上, 它可以非常有效率地處理快速傅立葉轉換（fast Fourier transform），此外，蝴蝶圖屬於Cayley圖的一類，Cayley圖[1]擁有許多好的拓樸性質，它非常適合作為平行或分散式系統的基礎拓樸結構。

一個r-維k-元蝴蝶圖（r-dimensional k-ary butterfly）以BF（k, r）來表示，它包含rk^r個點（vertex），這些點被放置在r層（level），每一個點（vertex）以v = <l, b₀b₁×××b_r-1>來表示，其中l Î {0, 1, …, r - 1}表示v的層（level），b_j Î {0, 1, ¼, k - 1}，0 £ j £ r - 1，表示它在該層的位置，二個點只會在相鄰的層有邊相連，更詳細的定義可參考[3, 4]。例如圖一為BF（2, 3）的結構。

大型的網路往往需要大量的通訊（communication），有效的通訊將會大大改善整個網路的效能。而通訊的方式最常使用的便是一對一的點與點之間傳遞訊息，二個點藉由網路的某一條路徑（path）來傳遞訊息，然而二點間的路徑往往有很多條，如何找到一條最短的路徑來傳遞訊息便成為一個很重要的問題。這個問題我們一般稱最短路徑問題（shortest path problem），這個問題對於一般的網路是屬於NP-complete的複雜度，但對於某些特定的網路可以很有效地解決，在此我們將報告有關蝴蝶圖上的最短路徑演算法（shortest path algorithm）。

給定BF（k, r）上的二個點s及t，其中s表示傳送訊息的起始點（source vertex），t表示接受訊息的終點（destination vertex），我們欲建構一條由s到t的最短路徑。首先我們建構二條由s到t的路徑，分別稱它們為L_Path及R_Path，然後證明這二條路徑中較短者即為BF（k, r）最短路徑。在此我們以BF（2, 3）為例子來說明這二種路徑。考慮BF(2, 3)中s = <1, 110>，t = <0, 000>，L_Path的路徑為s = <1, 110> ® <0, 110> ® <1, 010> ® <2, 000> ® <0, 000> = t，其長度為4。而R_Path的路徑為s = <1, 110> ® <2, 110> ® <1, 100> ® <0, 000> = t，其長度為3。R_Path的長度比L_Path來得短，所以R_Path即為s到t的最短路徑。詳細的演算法及證明可參考[3]。

參考文獻：

[1] S. B. Akers and B. Krishnamurthy, "A group-theoretic model for symmetric inter- connection networks, IEEE Transactions on Computers, vol. 39, no. 4, pp. 555-566, 1989.

[2] W. D. Hillis, The Connection Machine, MIT Press, Cambridge, MA, 1985.

[3] S. C. Hwang, "Some optimization problem on butterfly graphs", Ph. D. Thesis, Department of Computer Science of National Taiwan University, 2000.

[4] F. T. Leighton, Introduction to Parallel Algorith ms and Architecture: ArraysTrees Hypercubes, Mor gan Kaufman, San Mateo, CA, 1992.