贪心算法解决tsp问题的c语言代码自己输入矩阵

以下是一个简单的贪心算法解决TSP问题的C语言代码，可以手动输入距离矩阵：

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 100

int n; // 城市数量
int dist[MAX_N][MAX_N]; // 距离矩阵
int visited[MAX_N]; // 标记城市是否已经访问过
int path[MAX_N]; // 记录路径
int cost; // 记录最小花费

void input() {
    printf("请输入城市数量n：");
    scanf("%d", &n);
    printf("请输入距离矩阵：\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &dist[i][j]);
        }
    }
}

void tsp(int start) {
    // 初始化
    for (int i = 0; i < n; i++) {
        visited[i] = 0;
    }
    visited[start] = 1;
    path[0] = start;
    cost = 0;

    // 贪心选择
    for (int i = 1; i < n; i++) {
        int min_dist = -1;
        int next_city;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && (min_dist == -1 || dist[path[i-1]][j] < min_dist)) {
                next_city = j;
                min_dist = dist[path[i-1]][j];
            }
        }
        path[i] = next_city;
        visited[next_city] = 1;
        cost += min_dist;
    }

    // 回到起点
    path[n] = start;
    cost += dist[path[n-1]][start];
}

void output() {
    printf("最小花费为：%d\n", cost);
    printf("路径为：");
    for (int i = 0; i < n+1; i++) {
        printf("%d ", path[i] + 1);
    }
    printf("\n");
}

int main() {
    input();
    tsp(0); // 从城市0开始
    output();
    return 0;
}

程序中使用了一个 `dist` 数组来记录城市之间的距离，输入时需要手动输入。使用方法如下：

1. 先输入城市数量 `n`。
2. 然后输入 `n` 行，每行有 `n` 个数字，表示从第 $i$ 个城市到第 $j$ 个城市的距离。

例如，输入以下数据：

4
0 30 6 4
30 0 5 10
6 5 0 20
4 10 20 0

则程序输出结果为：

最小花费为：25
路径为：1 3 2 4 1 

其中，路径为从城市1出发，依次经过城市3、2、4，最后回到城市1。