解决多源多汇流网络的最佳方法 [英] Most optimal way to solve multiple-source multiple-sink flow network

问题描述

为简单起见，假设存在以下问题：

For the sake of simplicity, let's say we have the following problem:

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

We are writing the GPS for self-driving cars in a city. We assume the cars running our software are the only cars on the road.

它们的城市布局表示为流量网络，但流量网络具有多个起点/结束点，因此存在多个不一定彼此靠近的源/汇。

They layout of the city is represented as a flow network, but the flow network has multiple starting/ending points, so there's multiple sources/sinks that are not necessarily close to one another.

是否有解决此问题的有效方法？

Is there an efficient solution to this problem?

推荐答案

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

Standard approach to solving multiple source / multiple sink problems is adding a synthetic single source and a synthetic single sink. Once you connect synthetic source to all real sources with pipes of capacity equal to the capacity of the source, and also connect the synthetic sink to all real sink with a pipe equal to sink's capacity, you can use your preferred algorithm for solving single source / single sink flow network.

这篇关于解决多源多汇流网络的最佳方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！