Find Minimum cost to connect all cities in Python

In this tutorial, the aim is to find the minimum cost to connect all cities in Python.

Consider, that there are n cities in a state. Because of some natural disasters, all the roads connecting these n cities got destroyed. So, now there is no connection between any of the cities.

Aim: Our aim is to reconstruct the roads in such a manner that it will connect all cities and it should cost minimum.

Input: The input given will be a 2-D array, which consists of the cost to reconstruct roads between each city.
Each element of the 2-D array will of the form cost[I][j], which represents the cost between cities I and j.
cost[I][j] = 0 means, Even before natural disaster road doesn’t exist before I and j.

For example,

Input,

cost=
[[4, 0, 3, 9, 2, 5],
[3, 1, 0, 0, 3, 4],
[1, 0, 10, 0, 9, 7],
[0, 1, 2, 3, 4, 0],
[1, 0, 3, 1, 0, 4],
[0, 1, 3, 0, 1, 5]]

Output :  6

cost=
[[0, 0, 1, 8, 1, 2],
[2, 0, 0, 1, 1, 2],
[5, 0, 67, 0, 0, 5],
[0, 1, 9, 0, 0, 0],
[12, 9, 3, 2, 3, 3],
[0, 0, 32, 90, 56, 23]]

Output: 7

Expanation:

Here we use Minimum Spanning Tree (MST) algorithm to find the minimum cost. You can check: Kruskal’s Minimum Spanning Tree Algorithm in Python
This algorithm is used to connect all the provided nodes in a graph with the minimum possible edge weight.

def min_node(n, key_val, is_present): 
    min_val = 999999999999999
    min_index = None
      
    # Loop through all the values to find minimum valued one
    for i in range(n): 
        if (is_present[i] == False and 
            key_val[i] < min_val):  
            mini = key_val[i] 
            min_index = i 
    return min_index 
  
 # MST    
def mincost(n,cost):
    # Declaring an array of size n to store parent node of a particular node
    parent_node = [None]*n 
    
    # Declaring an array of size n to store whether each roads are present or not 
    # it will be an array with Boolean values
    is_present = [None]*n
    
    # Declaring an array of size n to store the key-value
    key_value = [None]*n 
    
    # We will each key value to infinity(high value) 
    # To avoid all roads initially, we will make Boolean array to False
    for i in range(n): 
        key_value[i] = 9999999999999999
        is_present[i] = False
        
    # Now we start from first Node
    # ie cost[0][0]
    # As cost[0][0] doesn't have a parent node, we set parent to -1
    # As minimum cost to reach cost[0][0] = 0, we assign key_value[0] to 0
    parent_node[0] = -1
    key_value[0] = 0  
    
    # Then for the remaining nodes
    for i in range(n-1):
        r = min_node(n, key_value, is_present)
        
        is_present[r] =True  #Updating when rth node is included
        
        # updating neighbouring nodes
        for k in range(n): 
            if (cost[r][k] and is_present[k] == False and 
                cost[r][k] < key_value[k]):  
                key_value[k] = cost[r][k]  
                parent_node[k] = r
    sum_cost = 0
    for i in range(1, n): 
        sum_cost += cost[parent_node[i]][i]  
    print(sum_cost) 
  
# Main Code 
if __name__ == '__main__': 
    
  
  # Sample input 
    n1 = 5
    sample_cost = [[4, 0, 3, 9, 2, 5],
                  [3, 1, 0, 0, 3, 4],
                  [1, 0, 10, 0, 9, 7],
                  [0, 1, 2, 3, 4, 0],
                  [1, 0, 3, 1, 0, 4],
                  [0, 1, 3, 0, 1, 5]]  
    mincost(n1, sample_cost)

Output: 6