解决多源多汇流网络的最优方法

Question

为了简单起见，假设我们有以下问题：

我们正在为城市中的自动驾驶汽车编写 GPS。我们假设运行我们软件的汽车是路上唯一的汽车。

他们将城市的布局表示为一个流动网络，但流动网络有多个起点/终点，因此存在多个不一定彼此靠近的源/汇。

这个问题有没有有效的解决方案？

Answer 1

解决多源/多接收器问题的标准方法是添加合成单源和合成单接收器。一旦您使用容量等于源容量的管道将合成源连接到所有真实源，并使用等于接收器容量的管道将合成接收器连接到所有真实接收器，您就可以使用首选算法来解决单源/单汇流网络。