K Centers Problem | Set 1 ( Greedy Approximate Algorithm ) | Python3 program for the above approach ; index of city having the maximum distance to it 's  closest center ; updating the distance of the cities to their closest centers ; updating the index of the city with the maximum distance to it 's closest center ; Printing the maximum distance of a city to a center that is our answer print ( ) ; Printing the cities that were chosen to be made centers ; Driver Code ; Function Call
def maxindex ( dist , n ) : NEW_LINE INDENT mi = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( dist [ i ] > dist [ mi ] ) : NEW_LINE INDENT mi = i NEW_LINE DEDENT DEDENT return mi NEW_LINE DEDENT def selectKcities ( n , weights , k ) : NEW_LINE INDENT dist = [ 0 ] * n NEW_LINE centers = [ ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT dist [ i ] = 10 ** 9 NEW_LINE DEDENT max = 0 NEW_LINE for i in range ( k ) : NEW_LINE INDENT centers . append ( max ) NEW_LINE for j in range ( n ) : NEW_LINE INDENT dist [ j ] = min ( dist [ j ] , weights [ max ] [ j ] ) NEW_LINE DEDENT max = maxindex ( dist , n ) NEW_LINE DEDENT print ( dist [ max ] ) NEW_LINE for i in centers : NEW_LINE INDENT print ( i , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 4 NEW_LINE weights = [ [ 0 , 4 , 8 , 5 ] , [ 4 , 0 , 10 , 7 ] , [ 8 , 10 , 0 , 9 ] , [ 5 , 7 , 9 , 0 ] ] NEW_LINE k = 2 NEW_LINE selectKcities ( n , weights , k ) NEW_LINE DEDENT