有向グラフ内のツリーパスのコストを最小化する

Question

負の重みと正の重みを持つ有向グラフを持っていますが、ルート（グラフのノード）が与えられたツリーで円弧のコストを最小限にしたいと考えています。

すべてのノードをカバーすることは重要ではないことに注意してください。私はブランチ/アークのコストを最小限に抑えたい。だからそれはMDSTではありません。

この問題の既知の名前は何ですか？

プログラミングを簡単にするためにInteger Formulationを探したいですか？

編集：ルートを指定すると、そのツリーのアークのコストを最小限に抑えるツリーを生成する必要があります。つまり、アークの合計を最小にするパスツリーを見つける必要があります。私が与えるExampのように、右上隅のノードに移動すると、両方の可能なパスで100のコストがかかるため、パスの値が大きくなります（最小化したい）。

類推：その島には、様々な宝物 （負の数）につながる複数のパス（アーク）があると考えてください。しかし、トラップ（正の数）宝のいくつか。可能な限り最大の宝を蓄積する道を探したい。

すべてのトラップを避けることはできません.100コインを失うパスを想像してください。そのパスは、10000コインを与える別のパスと結びついています。

最小スパニングツリーの問題と似ていますが、この場合は負の数もあります。グラフは向けられており、ソリューション内のすべてのノードをカバーする必要はありません。

Answer 1

1つのルートから他のルートへの重みの合計を調べたいと思います。負の重みのないグラフでは、Dijkstraのアルゴリズムで解くことができ、負の重みのグラフではBellman-Fordのアルゴリズムで解くことができます。私はこれが答えを見つけるのを助けることができると思います。