Most optimal way to solve multiple-source multiple-sink flow network

Question

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

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?

Answer 1

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.

Answer 2

Yes, you can create a single dummy source that all of your other sources connect to, and similarly, a single dummy sink for all of the real sinks to connect to.

But what flow do you assign to the edges from the dummy source to a real source? The edge from your dummy source to a real source (lets call it A) should have a flow equal to the sum of all edges leading out of A. Likewise, the flow of an edge from a real sink (B) to the dummy sink should be the same as the sum of all edges coming in to B.

You can read more about it in these lecture slides about network flow.