※ 引述《DJWS (...)》之铭言： : 你误会题意了。举个例子： : edge cost : 1 <--> 2 2 : 1 <--> 3 2 : 1 <--> 4 1 : 2 <--> 3 3 : 然後让 2 3 4 这三个节点相连通，所需要的最少 cost 应为 5。 : ※ 引述《tkcn (小安)》之铭言： : : 找出所有被选定的点之间的最短路径， : : 便可建出一个虚拟的 graph，而且是 complete graph， : : 找出 MST 再从虚拟的 edge 中找回对应的最短路径。 : : 实际写演算法的话， : : 可以不用真的去产生那虚拟的 graph， : : 只要将原先的 MST 搭配 all-pairs shortest path 产生的表格即可。 : : 有错请指正。 假设你要找2,3,4之间最小成本，所以找所有路径当中跟2,3,4有关的， 选成本最小的一条，这边是1 <--> 4，所以你现在收集了1跟4的点， 然後在搜寻有跟1,4当中有关的最小成本，这边是1 <--> 2 or 1 <--> 3 假设你选1 <--> 2，所以你现在手上有1,2,4三个点，然後再搜寻 跟1,2,4有关的路径当中成本最小的，最後得到1 <--> 3，总成本是5 所以我觉得应该是一开始你要先输入你需要哪先点相连，输入完再让它 搜寻跟这些点有关系当中成本最小的路径，所以每次搜寻应该就会连起来 一个你想要的点。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.114.53.85