十七世紀初期的某一天，法國大數學家費瑪 (Fermat) 正結束了一個有名的關於求最大最小值的演講，演講中他介紹了一個在各種曲線上不用微積分求切線的辦法。 他雄辯的向聽眾挑戰說：「誰不信我的辦法，就解這個問題給我看：給定平面上三點，找出第四點使得它和給定三點的距離之和為最小。」當費瑪丟出一個問題後，自然四方都有迴響。 1640年意大利的托里切里 (Torricelli) 用幾何方法證出第四點應是正三角形 ABD、BCE、CAF 的外接圓交點（圖一點 O，ABC 是三給定點）稱為托點。 1674年卡伐利立 (Cavalieri) 在他的《幾何演習》一書中指出 。 1750年辛普生(Simpson)證明托點也是 AE、BF、CD 三線的交點，這些線都叫做辛線。 1834年海能 (Heinen) 指出了以上結果都只有在 內角都不大於 時成立。當有一角 ，則托點即和此角之頂點重和。

圖一　托點的求法

他也證明了辛線長等於托點到 A、B、C 的總距離。

這一費瑪問題也有另一種提法，即「給定平面上三點，找到一個把這三點連結起來最短的網絡」。這時可證最短網絡即是托點和三給定點的連線。當我們把平面上三點推廣到平面上 n 點，這兩種提法卻形成了不同的問題。如果我們要找到一個托點使得該點和給定 n 點的總距離最短，這問題稱為廣義費瑪問題，非本文討論範圍。另一個問題是給定 n 點後找出連接該 n 點的最短網絡。這時連接一個托點到每個給定點不一定是最短的連法。譬如給定的四點是正方形的四頂點，則最短網絡是圖二(甲)而非(乙)。

圖二　正方形四頂點的最短網絡

為了和廣義費瑪問題區別，上述之最短網絡問題被稱為斯坦納問題（據考證斯坦納雖曾參與此問題但無顯著貢獻）。網絡中所含給定點（稱原點）之外的點叫做斯點。

我們首先看看最短的網絡應該具有那些性質。所謂一個網絡的拓樸即指點與點間連接的關係。因此在一個拓撲中斯點的位置並不固定，邊的長度也非所計，一個拓撲只規定了那些點間有邊相連。

(甲)

拓撲必須是樹形：所謂樹形即指沒有圈。因為如有圈，則我們可以去掉圈中任一條邊來縮短網絡而不影響任何點的連接。

(乙)

令 S 為網絡中的一斯點，則 S 的度數（即與 S 相交的邊數）至少為三： 如果S的度數為一，則去掉S上的邊不影響任何點的連接；如果S的度數為二，設計二邊分別連接U和V，則以線UV代替線 SU和線SV，縮短了網絡而不影響任何點的連接。

(丙)

與 S 相交的任兩邊其夾角不小於 120 度； 不然的話可在其兩夾邊上取 U,V 兩點使得 的內角皆小於 120 度。根據費瑪問題的結論，S、U、V 三點間的最短連接並非 SU 和 SV 兩邊， 因之現有網絡並非最短。

注意(甲)和(乙)合併考慮時，可導致n點的最短網絡至多含n-2斯點的結論； (乙)和(丙)合併考慮時，可導致每一斯點恰交三邊，且夾角都是120度的結論。

一個連接n原點的網絡如滿足(甲)(乙)(丙)三條件則稱為斯樹。 顯然的，最短網絡必須是斯樹，所以也可稱為最短斯樹。 有n-2個斯點的斯樹稱為滿斯樹。（滿）斯樹的拓撲稱為（滿）斯拓撲。

梅爾扎克 (Melzak) 給了一個從一個滿拓撲造出它的滿斯樹的算法， 這個算法即成為造n原點上的最短斯樹的基礎。 首先注意任何一個非滿的拓撲都可以分解成一些較小的滿拓撲。 每一個滿拓撲上的點集合都是非滿拓撲上的點集合的一個子集， 每一條非滿拓撲的邊都屬於且僅屬於一個滿拓撲。 下圖中顯示一個五點的非滿拓撲分解成一個四點和一個兩點（虛線）的滿拓撲。

圖三　非滿拓撲的分解

在每一個滿拓撲上用梅爾扎克算法造出它的斯樹，這些斯樹的聯合即為原來非滿拓撲的斯樹。

現在我們可以敘述造最短斯樹的算法： 「歷舉所有的斯拓撲（即每一斯點只有三條邊的拓撲），對應於每一斯拓撲用Melzak算法造出它的斯樹（有時不存在），這些斯樹中最短的一個即最短斯樹。」

尚未明述的一步是梅爾扎克造滿斯樹的算法。 令T為給定的斯拓撲。在n=3時梅爾扎克算法即同於托里切里對費瑪問題的解法。 當時梅爾扎克算法可以分成兩步。 第一步是遞歸的將兩原點換為一新原點，且新拓撲的斯點也減少一個， 所以仍為滿拓撲，直至只剩下兩原點為止。 細言之，令A、B為連接於同一斯點S的兩原點（總有如此兩點）， 設S連接的第三點為C。 令D為正三角形ABD的第三點且D與S分在AB線兩側。 新的滿拓撲T'由T去掉AS、BS、CS三邊再加上DC邊而得。 注意D點的位置是固定的，所以可視為一新的原點。 第二步是把第一步的順序倒過來，由兩原點的滿斯樹逐步還原成n原點的滿斯樹。 我們舉例說明。

圖四　梅爾札克造滿斯樹的算法

設 A、B、C、D 為給定四原點。 給定的拓撲T包含下列諸邊AS₁、BS₁、 S₁S₂、DS₂、CS₂。 梅爾扎克算法第一步（圖四A）將E代替A和B， 新的拓撲T'包含ES₂、DS₂、CS₂三邊， 再將F代替E和C。 剩下一個兩點F和D的拓撲包含邊FD， 第二步（圖四B）先作正三角形CEF的外接圓和邊FD交於S'₂， 再作正三角形ABE的外接圓與邊ES'₂交於S'₁。 令 t 為含邊 AS'₁、BS'₁、S'₁S'₂、DS'₂、CS'₂ 的樹。連續使用費瑪問題的結論，可知 t 為 T 的斯樹（即證 S'₁ 和 S'₂ 的邊的夾角都是120度）。

我們來檢查一下以上法造最短斯樹的複雜度 (complexity) 首先我們看看梅爾扎克造滿斯 樹算法的複雜度。 注意當我們把兩原點換成新點時，我們只知道這三點應構成一正三角形， 且新點應和 A、B 點共同連結的斯點分在邊 AB 的兩側。 但因一般說來在第一步操作時我們並不知道斯點的位置， 因此新點的位置有兩個可能（分別在邊 AB 兩側）。 同理下一次換點時又有兩個可能，如此推論， 則第一步的操作原則上要考慮 2^n-2 個可能。 當然在點數少時或在其它的幾何性質可以利用時， 往往可正確的判斷新點的位置， 但我們無法嚴格的計算這些可遇而不可求的機運來修正2^n-2這一數量。

另一個嚴重的計算問題是斯拓撲的數目太多。 用歸納法可以算出當原點數為 n、斯點數為 s 時， 共有 個斯拓撲。 當 n=7, s=5 時，這個數目是 945，但在 n=7 時我們需考慮所有 的拓撲。這個總數達到 62370。

這是否意味以上這一造最短斯樹的算法太差而應另起爐灶呢？ 事實上有一個理論上的結果顯示只能有量的改進而不會有質的變化了。 蓋瑞 (Garey)、葛立翰 (Graham) 和強生 (Johnson) 在1977年證明了造最短斯樹是一個計算科學上稱為 NP-complete 的問題。 簡言之，即這類問題最佳算法的複雜是 n 的一個冪數函數而非多項式函數。 當我們警覺到 2ⁿ 當 n=100 時已是一個有 30 個零的數字， 就知道造最短斯樹只有在 n 很小時才有可行性。用我們介紹的這一算法， n 的上限大約在 10 到 15 之間。

最近有一個已發現的改進和一個可能的改進可以將 n 的上限再往上推展一些。 已發現的是梅爾扎克造滿斯樹的算法可以改進到線性複雜度。 細言之，當拓撲含 s 斯點時，如果適當的選擇二原點，則新點應在二原點的那一側永遠可以確定，因此 2^n-2 種可能就減成只有一個可能。 這個結果筆者即將發表於《O.R. Letters》這一雜誌上。

另一個尚未完成，但若成功時其影響將遠大於前段所述之改進是，要證明造最短斯樹只需考滿斯拓撲即可。當最短斯樹的拓撲 T 非滿時，必定有一個滿斯拓撲的斯樹會蛻化成 T 的斯樹，因此也就是最短斯樹。如果上述構想為真，則在 n=7 時，我們只需考慮 s=5 的 945 種拓撲而非 的 62370 種拓撲。

談到斯坦納樹問題，不可不提一下斯率 (Steiner ratio)。 最短生成樹的定義是不許有斯點時連接原點的最短網絡。 斯率的定義是在任何原點集合下最短斯樹和最短生成樹長的比率。 在原點集合為正三角形的三頂點時，兩樹長的比率是 ， 因此斯率不能大於 。 1968年格爾伯特 (Gilbert) 和勃拉克 (Pollak) 猜測斯率即為 （約 .866）且報導了牧爾 (Moore) 的證明斯率大於 .5， 1976年葛立翰和筆者證了斯率大於 .577， 1978年鍾金芳蓉和葛立翰證了斯率大於 .743， 1983年堵丁柱和筆者證了斯率大於 .8。 1985年鍾金芳蓉和葛立翰證了斯率大於 .8241。 另一方面格爾伯特和勃拉克在1968證了 n=3 時斯率為 ， 1978年勃拉克又證了 n=4 的情形。 1985年堵丁柱，姚恩瑜和筆者證了 n=5 的情形。