贪心法求解TSP问题

#include<iostream> #include<iomanip> using namespace std; int main() { int n, i, j, u, v, min, edgecount = 0, tsplength = 0; cout << "顶点个数："; cin >> n; int *flag = new int[n]; for (int i = 0; i < n; i++) flag[i] = 0; int **arc = new int*[n]; for (int i = 0; i < n; i++) { arc[i] = new int[n]; } //输入图的代价矩阵 cout << "请以矩阵形式输入顶点之间的距离" << endl; for (i = 0; i < n; i++) for (j = 0; j < n; j++) cin >> arc[i][j]; //纠正用户输入的数据 for (i = 0; i < n; i++) arc[i][i] = -1; cout << "您输入的顶点之间的距离如下" << endl; for (i = 0; i < n; i++) { for (j = 0; j < n; j++) cout << setw(3) << arc[i][j]; cout << endl; } flag[0] = 1; u = 0; cout << "最短路径为：" << endl; cout << "0-->"; while (edgecount < n-1) { min = 100; for (j = 0; j < n; j++) { if ((flag[j] == 0) && (arc[u][j] != -1) && (arc[u][j] < min)) { v = j; min = arc[u][j]; //cout << min; } } tsplength += arc[u][v]; flag[v] = 1; edgecount++; cout << v << "-->"; u = v; } tsplength += arc[u][0]; cout << "0" << endl; cout << "最短路径长度为：" << tsplength << endl; return 0; }