查找無向加權樹中最長的路徑

-1

我有一棵樹，每個邊都被分配了一個權重（一個實數可以是正數或負數）。我需要一種算法來找到最大總重量的簡單路徑（即路徑中邊的權重總和最大的簡單路徑）。路徑開始或結束的節點沒有限制。查找無向加權樹中最長的路徑

我有一個可能的算法，但我不知道它的工作原理，我正在尋找一個證明。那就是：

選擇任意一個節點ü和運行DFS（û）發現，開始於ü的最大重量簡單的路徑。讓（u,v）成爲這條路徑。
運行DFS（v）查找最大重量簡單路徑，從v開始。讓這條道路成爲（v,z）。

然後（v，Ž）是最大權重的簡單路徑。該算法在圖的大小上是線性的。任何人都可以告訴我它是否有效，如果有，請給出證據？

說明：Longest Path Problem對於具有循環的一般圖是NP-Hard。但是，我只在這裏考慮樹木。

來源

2013-01-15 becko

我想[數學SE]（http：//math.stackexchange。com /）是一個更好的地方來討論算法和證明 – Veger

@Veger：我不確定它會更適合。我在這裏看到了有關算法和證明的很好答案，而不僅僅是Math.SE。無論如何，我只是在[math.SE]（http://math.stackexchange.com/q/279265/10063）上發佈了這個問題的一個副本。 – becko

如果允許負權重，然後考慮下面的例子：

a<->b : -5000 
a<->c : 1 
b<->d : 1 
b<->e : 1

最長路徑d < - >乙< - >電子與長度爲2

任意挑一個到開始。 DFS返回c，距離爲1.第二個DFS返回a，距離爲1.但是a <→c不是最長的路徑。

來源

2013-01-15 13:41:51 Khaur

正如你所說，最長的路徑問題是一般**的NP-Hard **。我在這裏談論的是一棵**樹，而不是一個有周期的通用圖。 – becko

@becko的確，我錯過了那個相當重要的部分。 – Khaur

@becko我編輯了我的答案，以提供一個反例，如果你允許負面權重。 – Khaur

這裏有一個證明它的工作原理。該算法找到一對節點x0，y0，使得max_x d（x0，x0）= max_y d（x0，y）（也就是說，x0和y0是彼此最遠的節點）。對於任何這樣的對，d（x0，y0）是直徑。證明：令x *，y *爲兩個節點s.t. d（x *，y *）是直徑。存在節點r和s，使得路徑看起來像x0-r-s-y0和x * -r-s-y *。假設d（x0，y0）爲d（x *，y *），那麼d（x0，y *）> d（x0，y0）或d（y *，x0）> d（y0，x0）事實上x0和y0是彼此最遠的點。因此d（X0，Y0）= d（X *，Y *）

來源

2013-01-15 14:46:59

如果你確定有在圖中沒有循環，我會嘗試這樣的：

function findLongestPath(tree) 
begin 

    all_paths := {} 

    for each neighbour 
     all_paths.append(create_path(this_node, findLongestPath(three - current_node)) 

    sort_descending(all_paths) 
    return all_paths[0]; 
end

該算法可以進一步優化以存儲最佳路徑而不是一組（取消存儲所有可能路徑和排序的需要）。

來源

2013-01-15 15:28:34 Tuto

查找無向加權樹中最長的路徑

回答

相關問題