邊的最小權重連通子集算法

考慮從加權連通圖G中找到邊的最小權重連接子集T的問題.T的權重是T中所有邊權重的和（（ a）爲什麼這個問題不僅僅是最小生成樹問題？提示：認爲負重邊緣。（B）給出一個有效的算法來計算從手動連接Sciena子集 T.邊的最小權重連通子集算法

（c）中的最小重量

的（a）生成樹最小化摘要樹的重量，但minimum weight connected subset - 每對路徑權重，所以我們可以重複使用相同的負邊來減少每對路徑？（b）額頭上的決定：運行dijkstra的alg n次，跟蹤前面的最短路徑對。似乎不是最好的一個，其他的想法 - 排序的所有邊緣和從最大的打算 - 嘗試刪除，並檢查連接...

來源

2011-01-26 yetanothercoder

你的問題是什麼？我們不會爲你做你的功課！ – templatetypedef 2011-01-26 20:32:45

我不認爲找到最短路徑將工作。選定的邊緣不一定必須在兩個節點之間形成簡單的路徑。例如：`1 - 2（-1）; 2 - 3（-2）; 2 - 4（-4）`：你會選擇所有的邊緣，但它們不會形成路徑。所以我不認爲這涉及到路徑，至少不是以非常明顯的方式。 – IVlad 2011-01-26 21:09:26

對於A部分：

與具有每邊考慮K3（三角形）重量爲-1。

什麼是MST和什麼是最小權重連接子集？

來源

2011-01-30 16:17:30

邊的最小權重連通子集算法

回答

相關問題