相关疑难解决方法(0)

我有一个无向的正边缘权重图(V,E),我想要一个覆盖顶点V的子集k的最小生成树(Steiner树问题).

我不是将生成树的大小限制为k个顶点; 而且我确切地知道MST中必须包含哪些 k个顶点.

从整个MST开始,我可以削减边缘/节点,直到我得到包含所有k的最小MST .

我可以使用Prim算法来获取整个MST,并开始删除边缘/节点,同时不破坏子集k的MST; 或者我可以使用Floyd-Warshall获得所有对最短路径并以某种方式结合路径.有没有更好的方法来解决这个问题？