作者DJWS (...)
看板Prob_Solve
标题Re: [问题] 一个图论的问题
时间Sun Dec 23 20:12:54 2007
谢谢你的回覆。 :)
如你所说，这个问题是给定一个图，并选定一些节点，
然後才要将这些节点两两都相连通。
我对你提供的方法还有一些疑问。
当选择「成本最小的一条路径」时，
这是指最短路径吗？
另外，如果「成本最小的一条路径」不只一条时，
该选择哪一条路径呢？
我再举个例子：
edge cost
1 <--> 4 2
2 <--> 4 2
3 <--> 4 100
1 <--> 5 3
2 <--> 5 3
3 <--> 5 3
若要将 1 2 3 相连通，最少的 cost 为 9。
依照你的演算法，
如果先选择了 1-4-2 这一条路径，
再选择 1-5-3 这一条路径，
答案便会是10。
（1-4-2是所有选定的点之间，最短的一条路径。
1-5-3则是第二短的路径当中字典顺序最小的。）
※ 引述《xu3jp68 (信箱爆炸..XD)》之铭言：
: ※ 引述《DJWS (...)》之铭言：
: : 你误会题意了。举个例子：
: : edge cost
: : 1 <--> 2 2
: : 1 <--> 3 2
: : 1 <--> 4 1
: : 2 <--> 3 3
: : 然後让 2 3 4 这三个节点相连通，所需要的最少 cost 应为 5。
: 假设你要找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.112.90.81
※ 编辑: DJWS 来自: 140.112.90.81 (12/23 20:15)
※ 编辑: DJWS 来自: 140.112.90.81 (12/23 20:19)
※ 编辑: DJWS 来自: 140.112.90.81 (12/23 20:23)
※ 编辑: DJWS 来自: 140.112.90.81 (12/23 20:27)