最輕的路徑樹

我需要編寫在有向圖和加權圖中找到最輕的路徑樹的算法。（應該儘可能高效）我得到一個頂點S，需要從S到所有可以從S接近的頂點構建一個路徑樹，因此樹中的路徑是最輕的（路徑權重是沒有路徑的路徑兩端）最輕的路徑樹

我想到了第一次計算所有從S距離，然後爲每個路徑都會有一個新的權重：的重量減去兩端，然後用新的權重圖運行Dijkstra算法.. 。

它會工作嗎？它有效嗎？如何計算距離？

2012-05-13 Nusha

你是從單一來源尋找[最小生成樹]（http://en.wikipedia.org/wiki/Minimum_spanning_tree）或[最短路徑]（http://en.wikipedia.org/wiki/Shortest_path_problem）？這些是不同的問題。確定解決方案A比解決方案B更好的標準是什麼？ – amit

@amit基本上我的問題中的每個頂點都有一個值（非負值）。然後我有S源頂點，我需要建立路徑樹到所有頂點可以從S – Nusha

的方法對於2給定的樹 - 你如何評價樹'T1'比樹'T2'好？什麼是標準？ – amit

您的意見建議您實際上是在尋找從單一來源到所有頂點的最短路徑。

看看Dijkstra's algorithm是如何工作的。該算法從大小爲1的樹開始（僅用於源），並迭代地將頂點添加到樹中。最後，由dijkstra算法創建的樹表示從源到圖中每個節點的最短路徑。

請注意，dijkstra的算法需要邊上的權重函數，而您的權重函數位於頂點上。通過定義一個新的權重函數w':E->R：w'(u,v) = w(u)（它可以工作，因爲你不想計算結束）。

來源

2012-05-13 18:44:23 amit

是複雜度與dijktra的算法相同嗎？ – Nusha

是的。它可以在dijkstra算法運行時創建，只要算法找到通往它的最短路徑，就可以通過向樹添加一個頂點。 – amit

這聽起來像你要求minimum spanning tree。維基百科頁面討論算法。

來源

2012-05-13 18:29:33 jrennie

其實，他的問題，特別是他的評論顯示他正在尋找到每個頂點的最短路徑，而標題只是誤導。（特別是評論：'從S到頂點的路徑應該是最便宜的） – amit

爲什麼誤導？這是我在問題中被問到的... – Nusha

最輕的路徑樹

回答

相關問題