C++ 商旅问题算法：使用 DFS 搜索最短路径

本文介绍使用 C++ 实现的商旅问题算法，该算法利用深度优先搜索 (DFS) 来寻找最短路径。

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
int ans = INF;
int n; // 城市数量
vector<vector<int>> Map; // 商旅问题的图
vector<int> path; // 当前路径
vector<bool> visited; // 记录是否已经访问过该城市

void dfs(int cur, int len) {
    // 本函数来计算最短路径长度
    if (len >= ans) return; // 剪枝
    if (path.size() == n) { // 所有城市都已经访问过
        ans = min(ans, len + Map[cur][0]); // 更新最短路径长度
        return;
    }
    for (int i = 1; i < n; i++) {
        if (!visited[i]) {
            visited[i] = true;
            path.push_back(i);
            dfs(i, len + Map[cur][i]);//这边开始用递推手法，有参考网络
            path.pop_back();
            visited[i] = false;
        }
    }
}
void readGraph(string filename){
    ifstream fin(filename); // 打开文件
    fin >> n; // 读取城市数量
    Map = vector<vector<int>>(n, vector<int>(n));
    visited = vector<bool>(n, false);
    path.push_back(0); // 从第一个城市出发
    //std::cout<<path.empty();
    visited[0] = true;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            fin >> Map[i][j]; // 读取图信息
        }
    }
    fin.close(); // 关闭文件
    dfs(0, 0); // 从第一个城市开始搜索
    cout << '最短路径长度为：' << ans << endl;
    path.clear();//经过同学指导，这里要重置path，35行那里还不够（卡了好久）
}

int main() {
    readGraph('Map1.txt');
    ans = INF;//每次得把ans重新变成正无穷，不然会导致，后面答案比前面大的话，会录入前面答案
    readGraph('Map2.txt');
    ans = INF;
    readGraph('Map3.txt');
    return 0;
}

算法的时间复杂度

这个算法的时间复杂度比较复杂，因为它是一个搜索算法，且使用了剪枝优化。如果所有城市都相邻，那么它的时间复杂度会达到 $O(n!)$，因为需要枚举所有路径。但是如果存在一些无法到达的城市，那么时间复杂度会低很多。

实际上，这个算法的时间复杂度很难精确计算，因为它的搜索路径是非常复杂的。但是，可以肯定的是，它的时间复杂度不会比 $O(n!)$ 更高，因为使用了剪枝优化。

综上所述，可以认为这个算法的时间复杂度为 $O(n!)$ 或者 $O(n!)$ 的一个较小常数倍数。