Scribd
Upload
16 views

TSP Using Bfs and Dfs

Travelling salesman

Uploaded by

Mohammed Vaseem
Copyright
© © All Rights Reserved
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
16 views

TSP Using Bfs and Dfs

Travelling salesman

Uploaded by

Mohammed Vaseem
Copyright
© © All Rights Reserved
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 13

TRAVELLING SALESMAN PROBLEM

a. Using BFS

AIM:

ALGORITHM:
OUTPUT:
PROGRAM:
from collections import deque
import itertools

def calculate_path_length(path, dist):


length = 0
for i in range(len(path) - 1):
length += dist[path[i]][path[i + 1]]
length += dist[path[-1]][path[0]]
return length

def traveling_salesman_bfs(dist):
n = len(dist)
all_cities = list(range(n))

queue = deque()
for i in range(n):
queue.append((i, [i]))

min_length = float('inf')
best_path = []

while queue:
current_city, path = queue.popleft()
if len(path) == n:
length = calculate_path_length(path, dist)
if length < min_length:
min_length = length
best_path = path
continue

for next_city in all_cities:


if next_city not in path:
queue.append((next_city, path + [next_city]))

return best_path, min_length


dist = [
[0, 25, 10, 15],
[25, 0, 10, 45],
[10, 10, 0, 5],
[15, 45, 5, 0]
]
best_path, min_length = traveling_salesman_bfs(dist)
print("Optimal Path : ", best_path)
print("Minimum Length Using BFS : ", min_length)

RESULT:
b.Using DSF
AIM:

ALGORITHM:

OUTPUT:
PROGRAM:
def calculate_path_length(path, dist):
length = 0
for i in range(len(path) - 1):
length += dist[path[i]][path[i + 1]]
length += dist[path[-1]][path[0]]
return length

def dfs_tsp(dist, current_city, path, visited, best_path, min_length):


n = len(dist)

if len(path) == n:

length = calculate_path_length(path, dist)


if length < min_length[0]:
min_length[0] = length
best_path[:] = path[:]
return

for next_city in range(n):


if not visited[next_city]:

visited[next_city] = True
path.append(next_city)

dfs_tsp(dist, next_city, path, visited, best_path, min_length)


visited[next_city] = False
path.pop()
def traveling_salesman_dfs(dist):
n = len(dist)
visited = [False] * n
best_path = []
min_length = [float('inf')]

for start_city in range(n):

visited[start_city] = True
dfs_tsp(dist, start_city, [start_city], visited, best_path, min_length)
visited[start_city] = False
return best_path, min_length[0]

if _name_ == "_main_":

dist = [
[0, 25, 10, 15],
[25, 0, 10, 45],
[10, 10, 0, 5],
[15, 45, 5, 0]
]
best_path, min_length = traveling_salesman_dfs(dist)
print("Optimal Path : ", best_path)
print("Minimum Length Using DFS: ", min_length)
RESULT:

You might also like