CODEWITHSUNDEEP
algorithmgraph
user1371666
user1371666

Reputation: 497

algorithm to deal with seating students for examination centre

Here is the situation. Say we have x students numbered 1,2...x living at fixed places in a city. There are y examination centres numbered 1 , 2 , 3 ...y with each having capacity 'i-can-hold[y]' respectively. distance of student i to examination centre j is 'i-have-to-walk[i][j]'

Can you suggest an algorithm which ensures that total distance travelled is minimum ? (i.e sum of distances of each student from their examination centres)

Obviously i-can-hold[1]+i-can-hold[2]+...+i-can-hold[y]>x

I am thinking of creating such a program that will enable least trouble to conduct examinations. Practical implementation is possible with help of googlemap.

Upvotes: 1

Views: 297

Answers (1)

fgb
fgb

Reputation: 18559

In general, without any constraints on the distance and capacities, this is a minimum-cost maximum-flow problem.

  • Each student and city is a vertex.
  • Each student is connected to a source with an edge of capacity 1, cost 0.
  • Each city is connected to a sink with capacity from i-can-hold, cost 0.
  • Each student is connected to a city with capacity 1, cost from i-have-to-walk.

The Ford–Fulkerson algorithm can be used to find the maximum flow, but doesn't take costs into account. It may help to learn it though to learn about flow networks with simpler examples.

There are many different algorithms for minimizing the cost. One is the "successive shortest path". The idea is to repeatedly find a minimum-cost path from the source to sink in the residual network, and add a flow along this path, until no more paths can be found.

For example:

Flow Network

a) A flow network where each vertex is labelled (cost, capacity). Contains a column of 3 students connected to a column of 2 centres.

b) Flow added along a shortest path (can be found with Bellman-Ford) in the residual network. The residual network is a graph created from the available capacity (capacity minus flow in each direction).

c) More flow added along another path.

d) The optimal flow. Flow has been added along a path which changes flow already added. This is allowed because the residual network has capacity in the opposite direction of the flow.

See also:

Upvotes: 5

Related Questions