from itertools import permutations

​

def calculate_distance(route, distances):

    total_distance = 0

    for i in range(len(route) - 1):

        total_distance += distances[route[i]][route[i + 1]]

    total_distance += distances[route[-1]][route[0]]

    return total_distance

​

def brute_force_tsp(distances):

    n = len(distances)

    cities = list(range(1, n))

    shortest_route = None

    min_distance = float('inf')

    for perm in permutations(cities):

        current_route = [0] + list(perm)

        current_distance = calculate_distance(current_route, distances)

        if current_distance < min_distance:

            min_distance = current_distance

            shortest_route = current_route

    shortest_route.append(0)

    return shortest_route, min_distance

​

distances = [

    [0, 2, 2, 5, 9, 3],

    [2, 0, 4, 6, 7, 8],

    [2, 4, 0, 8, 6, 3],

    [5, 6, 8, 0, 4, 9],

    [9, 7, 6, 4, 0, 10],

    [3, 8, 3, 9, 10, 0]

]

​

route, total_distance = brute_force_tsp(distances)

print("Route:", route)

print("Total distance:", total_distance)

​

#Python

#include <stdio.h>

#include <stdlib.h>

#include <limits.h>

​

#define NUM_CITIES 6

​

void swap(int *x, int *y) {

    int temp = *x;

    *x = *y;

    *y = temp;

}

​

int calculateDistance(int *route, int distances[NUM_CITIES][NUM_CITIES]) {

    int totalDistance = 0;

    for (int i = 0; i < NUM_CITIES; i++) {

        totalDistance += distances[route[i]][route[(i + 1) % NUM_CITIES]];

    }

    return totalDistance;

}

​

void copyArray(int *source, int *destination, int length) {

    for (int i = 0; i < length; i++) {

        destination[i] = source[i];

    }

}

​

void permute(int *array, int start, int end, int distances[NUM_CITIES][NUM_CITIES], int *shortestRoute, int *minDistance) {

    if (start == end) {

        int currentDistance = calculateDistance(array, distances);

        if (currentDistance < *minDistance) {

            *minDistance = currentDistance;

            copyArray(array, shortestRoute, NUM_CITIES);

        }

    } else {

        for (int i = start; i < end; i++) {

            swap((array + start), (array + i));

            permute(array, start + 1, end, distances, shortestRoute, minDistance);

            swap((array + start), (array + i)); // backtrack

        }

    }

}

​

int main() {

    int distances[NUM_CITIES][NUM_CITIES] = {

import java.util.ArrayList;

import java.util.Collections;

​

public class Main {

    public static int calculateDistance(ArrayList<Integer> route, int[][] distances) {

        int totalDistance = 0;

        for (int i = 0; i < route.size() - 1; i++) {

            totalDistance += distances[route.get(i)][route.get(i + 1)];

        }

        totalDistance += distances[route.get(route.size() - 1)][route.get(0)];

        return totalDistance;

    }

​

    public static void bruteForceTSP(int[][] distances) {

        int n = distances.length;

        ArrayList<Integer> cities = new ArrayList<>();

        for (int i = 1; i < n; i++) {

            cities.add(i);

        }

        ArrayList<Integer> shortestRoute = new ArrayList<>();

        int minDistance = Integer.MAX_VALUE;

        ArrayList<ArrayList<Integer>> allPerms = generatePermutations(cities);

        for (ArrayList<Integer> perm : allPerms) {

            ArrayList<Integer> currentRoute = new ArrayList<>();

            currentRoute.add(0);

            currentRoute.addAll(perm);

            int currentDistance = calculateDistance(currentRoute, distances);

            if (currentDistance < minDistance) {

                minDistance = currentDistance;

                shortestRoute = new ArrayList<>(currentRoute);

            }

        }

        shortestRoute.add(0);

        System.out.print("Route: ");

        for (int city : shortestRoute) {

            System.out.print(city + " ");

        }

        System.out.println("\nTotal Distance: " + minDistance);