斯坦納樹問題是組合最佳化問題，與最小生成樹相似，是最短網路的一種。最小生成樹是在給定的點集和邊中尋求最短網路使所有點連通。而最小斯坦納樹允許在給定點外增加額外的點，使生成的最短網路開銷最小。
問題的提出,定義,性質,套用,
問題的提出
平原上的三個城鎮間要興建一個公用的煤氣供應站，在選址問題上，要考慮的主要問題是使由供應站到三個城鎮的輸送管道的總長最短。如何去尋找合適地點？
假若要建的是一個垃圾處理站，要修建三條公路將垃圾站與三個城鎮連起來。這時，因為三個城鎮的居民的數目或工業性質等的不同，每天運送垃圾使用的車輛數目 各不相同，運輸的費用也就各異。因此，選取地點時，如果仍考慮使三條公路的總長最小，就不合理了。這時應該考慮：先計算出三個城鎮單位時間內生產的垃圾數 量的百分比（或每日運輸費用的百分比），如何選取地點，使得每個城鎮垃圾運輸數量與公路里程的乘積之和為最小。
1638年，法國數學家費馬在他所寫的一本關於求極值的書中就有了第一個問題，稱為費馬問題；第二個問題則到了18世紀中葉才由辛普森（A.R.Simpson）提出來。
定義
斯坦納樹問題的定義隨著歷史的發展在不斷的擴展和推廣。
- 瑞士數學家斯坦納（J.Steiner，1796—1863）將問題推廣成：在平面上求一點，使得這一點到平面 上給定的若干個點（稱為所與點）的距離之和最小。這可以看作斯坦納樹問題的雛形。
- 考慮到點的其他相關因素，加入了權重的表示。形成的推廣定義，德國的兩位數學家韋伯(H.Weber，1842—1913)和維斯菲爾德（E.Wieszfeld）分別在1909年和1937年將該問題作為工 廠選址問題提出來：某地有給定的若干個倉庫，每個倉庫的其他相關因素可以換算成一個權重表示，求一建造工廠的合適地點，使工廠到每個倉庫的距離與權重乘積 的總和最小，則這個工廠的地址是最經濟、便利的。
- 庫朗（R.Courant）和羅賓斯（H.Robbins）提出第一個定義中，斯坦納對此問題的推廣是一種平庸的推廣。要得到一個有意義的推廣，需要考慮的不是引進一個點，而應是引進若干個點，使引進的點與原來給定的點 連成的網路最小。他們將此新問題稱為斯坦納樹問題。給出的定義為：
假設原來已經給定了n個點，庫朗等指出需要引進的點數至多為n-2，此種點稱為斯坦納點。過每一斯坦納點，至多有三條邊通過。若為三條邊，則它們兩兩交成 120°角；若為兩條邊，則此斯坦納點必為某一已給定的點，且此兩條邊交成的角必大於或等於120°。其中最小的網路稱為已給定點的集合的最小斯坦納樹， 記作SMT。若此SMT的斯坦納點中有等於給定點的點，則稱此SMT為退化的，此給定點稱為退化點。
性質
Pollak-Gilbert猜想：
平面上任意n點集，斯坦納最小樹長與最小生成樹之長的比值的最小值是
問題的起源：1967年前，貝爾公司按照連結各分部的最小生成樹的長度來收費。同年，一家航空公司戳了貝爾公司一個大洞。當時這家企業申請要求貝爾公司增加一些服務點，而這些服務點恰恰位於構造該公司各分部的Steiner最小樹需增加的Steiner頂點上。這使得貝爾公司不僅要拉新線，增加服務網點，而且還要減少收費。這一意外事件迫使貝爾公司自此以後便採用了Steiner最小樹原則。
套用
此問題可以抽象為設ΔABC為等邊三角形，連結三頂點的路線（稱為網路）。這種網路有許多個，其中最短的路線顯然是二邊之和（如AB∪AC）。如何用最短的線路將三部電話連線起來？
解決方案：
但若增加一個周轉站（新點P），連線4點的新網路的最短路線為PA+PB+PC。最短路徑之長比原來只連三點的最短路徑要短。
這樣得到的網路不僅比原來節省材料，而且穩定性也更好。
