Рассчитать оптимальное расстояние и путь с возвратом

Question

Я должен рассчитать по названию, маршруту и ​​оптимальному расстоянию, используя алгоритм возврата. Трек гласит: Начиная с столицы острова, я должен посетить все острова архипелага (в декартовых координатах x и y) с наименьшими затратами и, наконец, вернуться в столицу.

Итак, я создалКласс Island, состоящий из строкового имени, двойного x и double y, и класса Archipelago, состоящего из столицы острова, векторных островков, вектора > distanceVectors, вектора optimPathBackTracking и double optimDistanceBackTracking = INT_MAX;

Итак, я написал этифункции, и я могу рассчитать расстояние идеально:

double min(double a, double b){
    if(a<b){
        return a;
    }else{
        return b;
    }
}

double calculateDistance(double x1,double x2,double y1,double y2){
    double distance = sqrt(pow(x2 - x1,2) + pow(y2 - y1,2));
    return distance;
}

// distanceVectors будет использоваться как матрица расстояний, где в индексе 0 будут расстояния, рассчитанные из столицы и последующие индексы, рассчитанные из этих

void populatesDistanceVectors(){
    vector<Isola> islandsTemp;
    islandsTemp.push_back(this->capital);
    for(int i = 0; i< islands.size();i++){
        islandsTemp.push_back(this->islands[i]);
    }
    for (int i = 0; i < islandsTemp.size(); i++){
    vector<double> vettoreDistanzeTemp;
        for (int j = 0; j < islandsTemp.size(); j++){
            vettoreDistanzeTemp.push_back(calculateDistance(islandsTemp[i].IsolaGetX(), islandsTemp[j].IsolaGetX(), islandsTemp[i].IsolaGetY(), islandsTemp[j].IsolaGetY()));
        }
     this->distanceVectors.push_back(vettoreDistanzeTemp);
    }
}

void tsp(vector<vector<double>> distanceVectors, vector<bool>& booleanVector, int currPos,
         long n, int count, double cost, double& ans){

    if (count == n && distanceVectors[currPos][0]) {
        ans = min(ans, cost + distanceVectors[currPos][0]);
        return;
    }
    for (int i = 0; i < n; i++) {            
        if (!booleanVector[i] && distanceVectors[currPos][i]) {
            booleanVector[i] = true;
            tsp(distanceVectors, booleanVector, i, n, count + 1,
                cost + distanceVectors[currPos][i], ans);
            booleanVector[i] = false;
        }
        cout<<endl;
    }
};

void calculateBacktrackingDistance(){
    populatesDistanceVectors();

    long numNodes = this->islands.size() + 1;
    vector<bool> booleanVector(numNodes);
    for (int i = 0; i < numNodes; i++){
          booleanVector[i] = false;
    }
    booleanVector[0] = true;
    tsp(distanceVectors, booleanVector, 0, numNodes, 1, 0, this->optimalDistanceBackTracking);

    cout << "optimal distance calculated with backtracking is : "<<this->optimalDistanceBackTracking<<endl;
}

Единственное, что я не могу сделать, это сохранить индексы «distanceVectors», используемые алгоритмом по порядку, чтобы получить точный порядок посещенных островов. Может ли кто-нибудь помочь мне с кодом? (возможно, изменив функцию tsp, чтобы сохранить точный порядок индексов в целочисленном векторе).

Спасибо

PS: за использованный алгоритм меня вдохновил этот источник https://www.geeksforgeeks.org/travelling-salesman-problem-implementation-using-backtracking/