旅行商问题c++并输出最短路径

旅行商问题（TSP）是一个著名的NP难问题，它的目标是寻找一条路径，使得经过所有城市且回到起点的总路径最短。由于它是NP难问题，因此没有一种通用的算法能够在多项式时间内求解，但是可以使用一些启发式算法来近似求解。

以下是使用贪心算法来近似求解TSP问题的C++代码，同时输出最短路径：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct Point {
    double x, y;
    Point() {}
    Point(double _x, double _y) : x(_x), y(_y) {}
};

// 计算两点之间的距离
double dist(Point p1, Point p2) {
    double dx = p1.x - p2.x;
    double dy = p1.y - p2.y;
    return sqrt(dx * dx + dy * dy);
}

// 贪心算法求解TSP问题
vector<int> tsp(vector<Point>& points) {
    int n = points.size();
    vector<int> path(n);
    for (int i = 0; i < n; i++) path[i] = i;
    double minDist = 1e9;
    do {
        double distSum = 0;
        for (int i = 0; i < n - 1; i++) {
            distSum += dist(points[path[i]], points[path[i+1]]);
        }
        distSum += dist(points[path[n-1]], points[path[0]]);
        if (distSum < minDist) {
            minDist = distSum;
        }
    } while (next_permutation(path.begin(), path.end()));
    return path;
}

int main() {
    vector<Point> points = {
        {0, 0},
        {1, 0},
        {2, 1},
        {1, 2},
        {0.5, 1.5}
    };
    vector<int> path = tsp(points);
    cout << "Shortest path: ";
    for (int i = 0; i < path.size(); i++) {
        cout << path[i] << " ";
    }
    cout << endl;
    cout << "Minimum distance: " << minDist << endl;
    return 0;
}

在上述代码中，我们使用了一个结构体`Point`来表示每一个城市的坐标。然后我们定义了一个函数`dist`用于计算两点之间的距离。接下来，我们使用贪心算法求解TSP问题，具体实现如下：

1. 首先，我们将所有城市的编号存储在一个数组中，并计算出这些城市的总数n。
2. 然后，我们使用STL中的`next_permutation`函数来生成所有可能的路径，对于每一条路径，我们计算它的总长度，并更新最短路径长度minDist。
3. 最后，我们输出最短路径以及对应的最小距离。

需要注意的是，这种方法是一种暴力枚举方法，对于城市数量较少的情况下可以使用，但是对于城市数量较大的情况下，时间复杂度会呈指数级增长，因此需要使用更高效的算法来近似求解TSP问题。