Search code examples
pythonalgorithmgraphminimumundirected-graph

Minimum cost to set internet in all rooms?

There are n rooms in a hostel. We want to supply internet to all the rooms, laying a proper network.

For each room 'i', we can either have a router directly with the cost 'router[i]', or connect that room through an ethernet cable pulled from another neighbor room’s router. The cost to lay ethernet cable between the two rooms is given by ethernet array, containing '(i, j, c)' which means it costs 'c' to lay ethernet cable between room 'i' and 'j' (or) 'j' to 'i'.

  • Connection is undirected, and we can have multiple ways to set the network up
  • At least 1 person has to take an initial router connection if everyone else intends to pull an ethernet cable from him.
  • If 1 person has pulled an ethernet from their neighbour, another neighbour of them also can pull ethernet from them. There's no limit/constraint on this chain.

Example:

minCostConnecting(n, router, ethernet)


n = 5
router = [1,2,1,5,3]
ethernet = [[2,4,1], [0,2,3], [1,3,3], [0,4,1]]

Output = 8

At Room 0 and Room 2, set up a router. Cost = router[0] + router[2] = 2 Connect rooms 0 and 4 at a cost of 1. At room 1 set up a router, with cost 2. From room 1 to 3, setup an ethernet cable at cost 3.

I am unsure of the best approach for solving this problem. I believe we need to at least lay internet in 1 room, and thought greedily choosing the cheapest room to lay the connection would work best? But then I am unsure how to connect the rooms properly given that we can also chain connections together?

Any sense of the algorithms/approaches here would be appreciated

Solution

  • Sounds exactly like MST problem. (Minimum Spanning Tree, for more info check the wiki -> https://en.wikipedia.org/wiki/Minimum_spanning_tree)

    Firstly I would make a directed weighted graph of the internet cost which the nodes are the rooms and the edges weight are the cost of the laying the ethernet between the two rooms.

    beside the rooms nodes I would add another node for the initial router with edges weight corresponding to the cost of the router in each room. this node guarantees that atleast one person has to take a router but also more than one person can buy another router (if it's cost effective).

    Now all is left is to find the MSP (takes O(m + n log n) using Prim's algorithm) and that's it