最小コスト フロー問題の修正されたインスタンスを有向グラフで解こうとしています。具体的には、送信元と送信先のペアは固定されており、各エッジには単位コストがありますが、容量は有限です。合計（フロー）/エッジを最小限に抑えたい。これに関連する 2 つのクエリがあります。
- 各フローがソースから宛先まで 1 つのパスを取る場合、どのように進めればよいですか? 1 つの解決策は、最短パス アルゴリズム (Dijkstra など) を使用することですが、フローを完全に収容できるパスのみを考慮します。これは、フローごとに繰り返し解決し、エッジ容量を毎回更新することで実行できます。最小コスト問題と最大フロー問題に関連する文献を確認しましたが、それらはすべて、任意の商品が任意のソースから任意の宛先に流れることができると仮定しています (同じタイプの商品の需要と供給を考えてください)。私の問題は、固定の送信元と送信先のペアが含まれていることです。この特定のケースのアルゴリズムはありますか?
- フローを分割することを検討している場合、つまり、各フローが複数のパスを取ることができる場合、どのような解決策がありますか?