The Travelling Salesman Problem | Brute-Force Method | Design And Analysis Of Algorithm | Sampad Kar
Full Code:
Travelling Salesman problem Using Brute Force Method
def shortest_tour(graph,start,end,path=None):
if path is None:
path = []
path = path + [start]
if len(path) == len(graph.keys()):
if end in graph[start]:
path.append(end)
return [path]
else:
return []
tour = []
for n in graph[start]:
if n not in path:
sp = shortest_tour(graph,n,end,path)
for s in sp:
tour.append(s)
return tour
def travelling_salesman(graph,cost,start):
end = start
res = shortest_tour(graph,start,end)
tour_cost = []
for i in res:
c = 0
for j in range(len(i)-1):
f = i[j]-1
t = i[j+1]-1
c+= cost[f][t]
tour_cost.append(c)
min_cost = min(tour_cost)
min_cost_path = res[tour_cost.index(min_cost)]
return min_cost,min_cost_path
if __name__=='__main__':
graph = {
1:[2,3,4],
2:[1,3,4],
3:[1,2,4],
4:[1,2,3]
}
cost = [
[0,10,15,20],
[10,0,35,25],
[15,25,0,30],
[20,25,30,0]
]
m_c,m_c_p = travelling_salesman(graph,cost,1)
print("The shortest Route: ",m_c_p)
print("The Cost Of Travelling: ",m_c)
#tsp #optimization #travellingsalesmanproblem #bruteforce #algorithms #graph #graphproblems #shortestpath #shortesttour #daa #cs #it #computerscience #dsa #coder #programmer #coding #programming #codingforlife #sampadkar