1

我正在尝试使用有向图解决最小成本流问题的修改实例。具体来说,源和目标对是固定的,每条边都有单位成本但容量有限。我想最小化总和(流量)/边缘。我有两个与此相关的查询:

  1. 如果每个流程从源到目的地都有一条路径,我应该如何进行?一种解决方案可能是使用最短路径算法(例如 Dijkstra),但只考虑可以完全适应流的路径。这可以通过迭代求解每个流并每次更新边缘容量来完成。我回顾了与最小成本和最大流量问题相关的文献,它们都假设任何商品都可以从任何来源流向任何目的地(考虑同类型商品的需求和供应)。我的问题是独一无二的,它包含固定的源和目标对。是否有针对这种特定情况的算法?
  2. 如果我考虑拆分流,即每个流可以采用多条路径,那么解决方案是什么?
4

0 回答 0