# Untitled

unknown
python
7 months ago
1.2 kB
2
Indexable
Never
```import math

def distance(city1, city2):
# Calculate Euclidean distance between two cities
return math.sqrt((city1[0] - city2[0])**2 + (city1[1] - city2[1])**2)

def nearest_neighbor(cities):
# Start from the first city in the list
current_city = cities[0]
path = [current_city]
total_distance = 0
unvisited_cities = set(cities[1:])

while unvisited_cities:
# Find the nearest unvisited city
next_city = min(unvisited_cities, key=lambda city: distance(current_city, city))
# Update the total distance and path
total_distance += distance(current_city, next_city)
current_city = next_city
path.append(current_city)
unvisited_cities.remove(next_city)

total_distance += distance(path[-1], path[0])
path.append(path[0])

return path, total_distance

# Example usage:
# Define a list of cities as (x, y) coordinates
cities = [(0, 0), (1, 5), (2, 3), (5, 1), (6, 6), (8, 3)]

# Find the path and total distance using the nearest neighbor heuristic
path, total_distance = nearest_neighbor(cities)

print("Path:", path)
print("Total distance:", total_distance)```