Untitled

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)

    # Return to the starting 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)