最小化有向图中树路径的成本
我有一个加权有向图，带有负值和正值权重，我想用给定根的树（图中的节点）来使弧的成本最小化。
请注意，覆盖所有节点并不重要。 我想尽量减少分支/弧线的成本。 所以这不是一个MDST。
这个问题的知名度是什么？
想要找到Integer表达式来简化编程。
编辑：为了澄清更多，给定一个根，我需要生成一棵树，以最小化该树中的弧的成本...换句话说，我需要找到一个最小化弧的总和的路径树。 在考虑我给，路径不会去右上角节点导致它在两个可能的路径中花费100，这将增加我的路径值（我想最小化它）。
比喻：想一个岛上的人，在那个岛上有多条路径（圆弧）可以产生各种宝物（负数），但是在一些陷阱（正数）的路径中，我们会失去一些宝藏。 我想找到一条积累最大宝藏的道路。
请记住，我们不能避开所有的陷阱，想象一条我们失去100个硬币的路径，但是那条路径与另一个给我们10000个硬币相连接。
这就像最小生成树问题，但在这种情况下，我也有负数，该图是定向的，我不需要覆盖解决方案中的所有节点。
我认为你想找出从一个根到另一个根的权重总和。 对于没有负权重的图，可以用Dijkstra算法求解，对于负权重图，可以用Bellman-Ford算法求解。 我认为这可以帮助你找到答案。
链接地址: http://www.djcxy.com/p/35223.html