結論 をポテンシャルとして の最大値を求める問題は、 を始点としてへの最短路長を求める問題の双対問題（dual problem）となる。 前提 線形計画問題（以下 LP ）: の行列 次元のベクタ 次元のベクタ が与えられ、 の制約下において、 objective function を…