假设：一个图G=(V,E,d)，其中d是非负边长，顶点子集S是Terminal集合，希望找到G中的一棵子树，包含S，且最小。

算法：

Step 1: 对S中每对点(u,v)，计算在G中的最短路P(u,v)及其长度d'(u,v)，得到S上的带权完全图G'=(S,E',d')；

Step 2: 构造G'的最小生成树T；

Step 3: 把T中的所有边(u,v)恢复为最短路P(u,v)，得到G的子图T'；

Step 4: 在T'中构造最小生成树T''；

Step 5: 在T''中去掉不必要的顶点，得到一棵包含S的树，作为输出。

近似比的证明非常巧妙。

 Reference: 

Kou, L., Markowsky, G., Berman, L.: A Fast Algorithm for Steiner Trees. Acta Inf. 15, 141–145 (1981)

转载本文请联系原作者获取授权，同时请注明本文来自刘兴武科学网博客。

链接地址：https://wap.sciencenet.cn/blog-3526448-1366987.html?mobile=1

收藏

分享