MinimumCostToConnectAllCities.py

# Python3 code to find out minimum cost
# path to connect all the cities
# Algorithm explanation https://www.geeksforgeeks.org/minimum-cost-connect-cities/
import sys

def minKey(n,list,nodes):
    min = sys.maxsize
    for i in range(n):
        if(list[i] < min and nodes[i] == False):
            min = list[i]
            index = i
    return index

def findcost(n , graph):
    # nodes used to make sure we don't same edge again when going to diffrent node ex: 1-0 AND 0-1 are share same edge
    nodes = [False] * n
    # first index is zero so we can compre it in minKey() also we only need N-1 edge so forst index will not matter
    list = [sys.maxsize] * n
    list[0] = 0
    sum = 0

    # loop through all nodes
    for count in range(n):

        # make sure we do not go through the same node again by checking nodes[] bool value
        u = minKey(n,list,nodes)
        # make it true so we do not go through same node
        nodes[u] = True

        # loop through all nodes and check their minimum edge
        for i in range(n):
            if (graph[u][i] > 0 and    nodes[i] == False     and  list[i] > graph[u][i]):
            #     edge exists    |  the edge hasn't been used |  less than the already exists in the list
                list[i] = graph[u][i]


# Find out the cost by adding the edge values 
    for i in list:
        sum += i
    print(sum)



if __name__ == '__main__':

    
    n1 = 5
    city1 = [[0, 1, 2, 3, 4],
             [1, 0, 5, 0, 7],
             [2, 5, 0, 6, 0],
             [3, 0, 6, 0, 0],
             [4, 7, 0, 0, 0]]
    findcost(n1, city1)

    
    n2 = 6
    city2 = [[0, 1, 1, 100, 0, 0],
             [1, 0, 1, 0, 0, 0],
             [1, 1, 0, 0, 0, 0],
             [100, 0, 0, 0, 2, 2],
             [0, 0, 0, 2, 0, 2],
             [0, 0, 0, 2, 2, 0]]
    findcost(n2, city2)