Graph with n people and k directions

Question

In the connected graph there are n points where hungry people stand. Every hungry person wants to go to one of the k restaurants on the chart. Travel distance should be within 1 km for each person. The restaurant can accommodate no more than guests at CEILING [n / k].

Provided that the points of these hungry people and restaurants in the area have an effective algorithm that works for polynomial time, which tells whether there can be EVERY guest (as in True or False)?

This view reminds me of the Traveling Salesman issue, is it just a modified version?

Answer 1

This is an example of a matching problem on a bipartite graph. This is much easier to solve than the traveling salesman problem, and can be done in O ((n + k) ^ 3).

There are two subtasks:

• Find people who can reach every restaurant.
• Find how to map people to restaurants to avoid overflowing restrictions.

Reaching Restaurants

You can calculate the shortest path between any pair of points in O (n ^ 3) using, for example, the Floyd-Warsall algorithm .

Permitted comparisons are compounds of distances less than 1 km.

Matching People to Restaurants

This coincidence problem can be solved by plotting and then solving for maximum flow.

The corresponding graph must have a node source, a node and node receiver for each person and each restaurant.

• Connect the source to each person with a capacity of 1
• Connect each person to each restaurant within 1 km with a capacity of 1
• Connect each restaurant to a sink with Ceil (n / k) capacity.

Then calculate the maximum flow through this graph. Each guest can be placed if and only if the maximum flow is n.

There are many algorithms for calculating the maximum flow. One example would be a push-relabel with complexity O (V ^ 3), where V is the number of vertices (V = n + k + 2 in this problem).