Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
# 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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment