最小生成樹害怕負重嗎？

我認爲最短路徑（SP）有負權重的問題，因爲它將路徑上的所有權重相加，並試圖找到最小路徑。

但我不認爲最小生成樹（MST）在負權重方面存在問題，因爲它只需要單個最小權重邊而不關心總權重。

我對不對？

考慮[計算機科學@ stackexchange]（http://cs.stackexchange.com/）？ – HongboZhu

@HongboZhu是啊，也許下一次 –

順便說一句，當圖中所有的邊都是負數時，找到最短路徑與尋找最長路徑的問題是一樣的，其邊界標有絕對值的原始長度。已知最長路徑問題是NP難題。 – Palec

是的，你說得對。 MST的概念允許任意標誌的權重。用於查找MST的兩種最流行的算法（Kruskal's和Prim's）可以在負邊緣上正常工作。

實際上，你可以在你的圖的所有邊上添加一個很大的正常數，使所有的邊都是正的。 MST（作爲邊緣的一個子集）將保持不變。

2012-05-02 12:54:21 Skiminok

事實上，作爲圖的子圖的樹具有取決於頂點數量的固定數量的邊緣，因此向每個邊緣成本添加數字「p」會增加「pE」的總體mst成本。找到最短路徑並不正確，因爲最短路徑可以由不同數量的邊組成。 – enedil

找到MST的兩種最流行的算法（Kruskal's和Prim's）可以在負邊緣上正常工作，因爲它們在無向圖上工作 – raghavsood33

是的，你是對的，因爲如果你看到像dijkstera這樣的最短路徑算法，它會檢查當前頂點v的距離是否大於當前值+邊權重的總和，那麼它會改變頂點距離的值v從s的總和值，如果邊的權重爲負，那麼它會帶來一些問題。

但是在MST問題中存在像prim，kruskal這樣的算法，這些算法只取最小權重邊緣，從而使負邊緣適合於MST。

2017-02-13 08:05:19

回答