Rani_exp9.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int calculateDistance(vector<vector<int>>& graph, vector<int>& path) {
    int distance = 0;
    int n = graph.size();
    for (int i = 0; i < n - 1; ++i) {
        int src = path[i];
        int dest = path[i + 1];
        distance += graph[src][dest];
    }
    distance += graph[path[n - 1]][path[0]];
    return distance;
}

int tspNaive(vector<vector<int>>& graph, int start) {
    int n = graph.size();
    vector<int> path(n);
    for (int i = 0; i < n; ++i)
        path[i] = i;

    int minDistance = INT_MAX;

    do {
        if (path[0] == start) {
            int distance = calculateDistance(graph, path);
            minDistance = min(minDistance, distance);
        }
    } while (next_permutation(path.begin() + 1, path.end()));

    return minDistance;
}

int main() {
    vector<vector<int>> graph = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };
    
    int startCity = 0;
    int minDistance = tspNaive(graph, startCity);
    
    cout << "Minimum distance: " << minDistance << endl;
    
    return 0;
}