Minimize cost of tree path in a digraph
I have a weighted directed graph, with negative and positive weights, i want to minimize the cost of the arcs with a tree given the root ( node in graph).
Note that covering all the nodes is not important. I want to minimize the cost of branchs/arcs. So it's not a MDST.
What's the know name for this problem?
Want to find the Integer Formulation to make programming easier.
Edit: To clarify more, given a root, i need to generate a tree that minimize the cost of arcs in that tree... In other words, i need to find a path tree that minimize the sum of arcs. Like in examble that i give, the path dont go to right upper corner node cause it cost 100 in both possible paths and this will increase my path value (i want to minimize it).
Analogy: Think a person in an island, in that island there are multiple paths(arcs) that leads to various treasures (negative numbers), but in some paths that are traps (positive numbers) that costs us to lose some of the treasure. I want to find a path that accumulate the maximum treasure possible.
Keep in mind that we cant avoid all traps, imagine a path that we lose 100 coins but that path is connected with another that give us 10000 coins.
It's like the Minimum Spanning tree problem, but in this case i have negative numbers too, the graph is directed and i dont need to cover all nodes in solution.
I think that you want to find out the sum of the weight from one root to the other root. For the graph without negative weight, it could be solved with Dijkstra's algorithm, and for the graph with negative weight, it could be solved with Bellman–Ford's algorithm. I think this can help you find the answer.
链接地址: http://www.djcxy.com/p/35224.html上一篇: 最短路径上的变化（复杂？）
下一篇: 最小化有向图中树路径的成本