# Solve K Centers problem in Python

Hi everyone, in this tutorial we are going to discuss the K Centers problem in Python and see how we can solve it.

In brief, we can be called K Centers as Metric k Center problem which is an NP-Hard Problem.

Given p dots, we need to choose k (k<=p) centers, such that the maximum distance of a dot to the center is minimized. In layman terms, say we need to build k warehouses given a map of p connected dots. The best way to build a warehouse is by keeping in mind that, it must be closest to the dots. In other words, the maximum distance of a dot to the warehouse must be minimal.

First of all, take a look at an example of the K Center image. Now we will be looking at a greedy approach towards this problem

1. Pick an arbitrary center, p1.
2. For every remaining dots P1, P2,… PN-, compute the minimum distance from the centers chosen already.
3. Pick the new center with the highest distance from already chosen centers, that is max((dist(p1, P1), dist(p1,P2), … dist(p1, pN-1)).
4. Continue this procedure until all the k centers are found.

Here is one of the important factors that we need to understand that this greedy approach has an approximate factor 2.

## Code in Python for K Center problem

Below is our Python program:

```import networkx as pt
import matplotlib.pyplot as pst
import operator

def k_centers_prob(V, n):
centers = []
cities = V.nodes()
centers.append((V.nodes()))
cities.remove(centers)
n = n-1
while n!= 0:
city_dict = {}
for cty in cities:
min_dist = float("inf")
for c in centers:
min_dist = min(min_dist,V[cty][c]['length'])
city_dict[cty] = min_dist
new_center = max(city_dict, key = lambda i: city_dict[i])
centers.append(new_center)
cities.remove(new_center)
n = n-1
return centers
def cGraph():
V = pt.Graph()
f = open('input.txt')
wtMatrix = []
for i in range(n):
wtMatrix.append(list1)
for i in range(n) :
for j in range(n)[i:] :
return V, noc
def dGraph(V, centers):
pos = pt.spring_layout(V)
color_map = ['blue'] * len(V.nodes())
for c in centers:
color_map[c] = 'red'
pt.draw(V, pos, node_color = color_map, with_labels = True)
edge_labels = pt.get_edge_attributes(V, 'length')
pt.draw_networkx_edge_labels(V, pos, edge_labels = edge_labels, font_size = 11)

#main function
if __name__ == "__main__":
V,n = cGraph()
c = k_centers_prob(V, n)
dGraph(V, centers)
pst.show()```
```Input:
4
0 10 7 6
10 0 8 5
7 8 0 2
6 5 12 0
3```

You can also be referred to: