斯坦纳树问题

（理学 | 计算机科学技术）

斯坦纳树问题（Steiner tree problem,STP），理学-计算机科学技术-计算机科学理论-算法-图算法，以瑞士数学家J.斯坦纳（Jakob Steiner，1796-03-18～1863-04-01）命名的图论中的经典组合优化问题（见组合优化）。同最小生成树相似，是最短网络的一种（见网络设计）。最小生成树是在给定的点集和边中寻求最短网络使所有点连通，而最小斯坦纳树允许在给定点外增加额外的点，使生成的最短网络开销最小。