max_i x_i - min_i x_i を最小化するために Bellman-Ford を使用したいとします。
変数 x_1、x_2、... x_n (変数の合計 n 個)
x_i - x_j <= c_{i,j} の形式の m 制約に従う
ここで、c_{i,j} は指定された定数で、負になる可能性があります。
Bellman-Ford を使用してこの種の問題を O(n*m) 時間で解決できることをどのように証明できますか?
私は次のことを試しました：
すべての変数 x_i に対してノード i を作成します
ソースノードを作る
s から他のすべてのノードへの重み 0 のエッジを作成する
この後どうすればいいのかわからない...助けてください、ありがとう。