1樓：
樓上說的最短路徑和最小生成樹其實都是可用的近似演算法。
其中mst是2-opt的，即cost不超過2倍的optimal Steiner tree的cost
如果把題目的三角形不等式約束拋棄，那麼每兩點的short path構成的graph和mst 都是c-opt的.
2樓：李庚辰
瀉藥，但是我是蒟蒻QAQ
看了下題目，果然很像Steinertree，嘛具體的上面已經有大佬給出了
推薦一道題：WC2008遊覽計畫，嘛應該是差不多的題目。
= =都說了我是蒟蒻不會這些問題。。。
3樓：
1.Dijkstra演算法能得出最短路徑的最優解，但由於它遍歷計算的節點很多，所以效率低。
2.SPFA（Shortest Path Faster Algorithm）（佇列優化）演算法是求單源最短路徑的一種演算法，它還有乙個重要的功能是判負環（在差分約束系統中會得以體現），在Bellman-ford演算法的基礎上加上乙個佇列優化，減少了冗餘的鬆弛操作，是一種高效的最短路演算法。
*補充:Bellman - ford演算法是求含負權圖的單源最短路徑演算法，效率很低，但容易實現。
以上均為搜尋所得，離散數學只接觸過第一種。記得大學第一堂專業課是C語言，老師讓我們學會並勤用搜尋引擎。
乙個連通圖有n個頂點，n 8條邊，權值各不相同，如何設計O n 的演算法計算最小生成樹
趙馮平 1.做9輪冒泡，把最大的9條邊 冒泡 到最後位置，這時前面n 1條邊是無序的，但其權值小於後面9條邊，而後面9條邊是按權值從小到大排序的。進行了9 n次冒泡操作，複雜度O n 生成的邊的序列成為A，A的每個元素包含邊的起點 終點及權值。2.類似克魯斯卡爾演算法，按第1步生成的順序A中，從頭到...
乙個頂點三條稜的立體有哪些，與頂點個數n的關係是如何
乘著歌聲的翅膀 5月21日補充 如果題主想問n取不同值的時候，滿足乙個頂點為三條稜的多面體有多少種 同坯的算一種 的話。難算，現在沒有好的公式表達。但可以肯定的是n為奇數時，a n 0。之前答案講過，因為這類多面體的對偶多面體三角面多面體，所以如果你題目裡的這個n指的是面的話，這個問題就等價於n個頂...
如何證明連通的這兩個等價刻畫？
自學生 用我發現了 時間生命是一對同在的自然法則 的一對時間統一標準原理模型觀點。陀螺儀標準系統原理模型，是一對時間生命執行變化過程系統模型，是一對正中和正反同在的自然法則標準原理系統，是一對核心心和外殼面連通原理模型，都是一對六份統一標準同在的半徑時間週期，都是六份統一存在時間數學半徑層面立方體模...