编辑代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int calPathLen(vector<vector<int>> cityMap, vector<int> path) {
    int len = 0;
    for (int i = 0; i < path.size() - 1; ++i) {
        len += cityMap[path[i]][path[i+1]];
    }
    return len;
}

void tsp(vector<vector<int>> cityMap, 
         int dstCity, 
         vector<int>& curPath,
         int& shortestPathLen, 
         vector<vector<int>>& shortestPaths) { 

    if (curPath.size() == 0) {
        curPath.push_back(dstCity);
    }
    int curLen = calPathLen(cityMap, curPath);

    if (curLen > shortestPathLen) {
        return;
    }
    //所有的城市添加到路径中，问题找到一个解
    if (curPath.size() == cityMap.size()) {
        // 将终点加入路径
        curPath.push_back(dstCity);
        // 计数当前路径长度
        int len = calPathLen(cityMap, curPath);
    
        if (len < shortestPathLen) {
            shortestPaths.clear();
            shortestPaths.push_back(curPath);
            shortestPathLen = len;
        }
        else if (len == shortestPathLen) {
            shortestPaths.push_back(curPath);
        }

        curPath.pop_back();

        return;
    }

    //添加一个城市到路径中，以减小问题规模
    for (int i = 0; i < cityMap.size(); ++i) {
        if (find(curPath.begin(), curPath.end(), i) == curPath.end()) {
            curPath.push_back(i);
            tsp(cityMap, dstCity, curPath, shortestPathLen, shortestPaths);
            curPath.pop_back();
        }
    }

}

void printTspResult(int pathLen, vector<vector<int>> paths) {
    cout << "最短路径长度： " << pathLen << endl;
    for (int i = 0; i < paths.size(); ++i) {
        int j = 0;
        for (; j < paths[i].size() - 1; ++j) {
            cout << paths[i][j] << "->";
        }
        cout << paths[i][j] << endl;
    }
}
int main() {
    // 旅行商地图1
    vector<vector<int>> cityMap1 {
        {0,30,6,4},
        {30,0,5,10},
        {6,5,0,20},
        {4,10,20,0},
    };
    int shortestPathLen1 = INT_MAX;
    vector<vector<int>> shortestPaths1;
    vector<int> curPath1;

    tsp(cityMap1, 0, curPath1, shortestPathLen1, shortestPaths1);
    printTspResult(shortestPathLen1, shortestPaths1);

    cout << "=================================================" << endl;
    // 旅行商地图2
    vector<vector<int>> cityMap2 {
        {0,8,5,36},
        {6,0,8,5},
        {8,9,0,5},
        {7,7,8,0},
    };
    int shortestPathLen2 = INT_MAX;
    vector<vector<int>> shortestPaths2;
    vector<int> curPath2;

    tsp(cityMap2, 0, curPath2, shortestPathLen2, shortestPaths2);
    printTspResult(shortestPathLen2, shortestPaths2);


	return 0;
}