作者DJWS (...)
站内Prob_Solve
标题Re: [问题] 一个图论的问题
时间Sun Dec 23 12:54:15 2007
你误会题意了。举个例子：
edge cost
1 <--> 2 2
1 <--> 3 2
1 <--> 4 1
2 <--> 3 3
然後让 2 3 4 这三个节点相连通，所需要的最少 cost 应为 5。
※ 引述《tkcn (小安)》之铭言：
: ※ 引述《DJWS (...)》之铭言：
: : 给定一个无向图，edge都有cost。
: : 现在在图上已选定了一些节点，我们想要把这些节点连接起来，让它们两两都相连通。
: : 请问最少的cost为多少？
: : 这个问题跟minimum spanning tree的差别是，
: : minimum spanning tree需要串起图上所有节点，
: : 而这个问题只需串起选定的节点即可。
: : 请问这个问题该如何解决？
: 找出所有被选定的点之间的最短路径，
: 便可建出一个虚拟的 graph，而且是 complete graph，
: 找出 MST 再从虚拟的 edge 中找回对应的最短路径。
: 实际写演算法的话，
: 可以不用真的去产生那虚拟的 graph，
: 只要将原先的 MST 搭配 all-pairs shortest path 产生的表格即可。
: 有错请指正。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.90.81
※ 编辑: DJWS 来自: 140.112.90.81 (12/23 12:54)