儘量減少有向圖中的樹路徑的成本

Question

我有一個加權有向圖，帶有負值和正值權重，我想用給定根的樹（圖中的節點）來使弧的成本最小化。

注意，覆蓋所有的節點並不重要。我想盡量減少分支/弧線的成本。所以這不是一個MDST。

這個問題的知名度是什麼？

想要找到整數表達式來簡化編程。

編輯：爲了澄清更多，給定一個根，我需要生成一棵樹，以最小化該樹中的弧的成本...換句話說，我需要找到一個最小化弧的總和的路徑樹。在考慮我給，路徑不會去右上角節點導致它在兩個可能的路徑中花費100，這將增加我的路徑值（我想最小化它）。

比喻：想一個人在一個島上，在那個島上有多條路徑（弧線），導致各種各樣的珍寶 （負數），但在一些路徑陷阱（正數），使我們輸了一些寶藏。我想找到一條積累最大寶藏的道路。

請記住，我們不能避免所有的陷阱，想象一條路徑，我們失去100個硬幣，但該路徑與另一個給我們10000個硬幣連接。

這就像最小生成樹問題，但在這種情況下，我也有負數，圖是直接的，我不需要覆蓋解決方案中的所有節點。

Answer 1

我認爲你想找出從一個根到另一個根的權重總和。對於沒有負權重的圖，可以用Dijkstra算法求解，對於負權重圖，可以用Bellman-Ford算法求解。我認爲這可以幫助你找到答案。