假设有五个地点,分别为A、B、C、D、E,用c语言编写五个地点之间的求出旅行距离最短,并打印最近路径
时间: 2024-01-26 07:01:49 浏览: 51
这是一个典型的最短路径问题,可以使用Dijkstra算法来解决。下面是C语言实现的伪代码:
```
#define INF 0x3f3f3f3f // 定义无限大
int n = 5; // 地点数量
int graph[5][5] = { // 五个地点之间的距离矩阵
{0, 10, INF, 30, 100},
{INF, 0, 50, INF, INF},
{INF, INF, 0, INF, 10},
{INF, INF, 20, 0, 60},
{INF, INF, INF, INF, 0}
};
int dist[5]; // 存储起点到每个地点的最短距离
bool visited[5]; // 标记每个地点是否已经访问过
// 初始化
for (int i = 0; i < n; i++) {
dist[i] = graph[0][i]; // 起点到每个地点的距离
visited[i] = false; // 初始时都未访问过
}
visited[0] = true; // 起点已经访问过
// 开始搜索
for (int i = 1; i < n; i++) {
int minDist = INF;
int minNode = -1;
for (int j = 0; j < n; j++) {
if (!visited[j] && dist[j] < minDist) { // 找到未访问过的距离最小的地点
minDist = dist[j];
minNode = j;
}
}
if (minNode == -1) break; // 找不到最小值,则退出
visited[minNode] = true; // 标记为已访问
for (int j = 0; j < n; j++) {
if (!visited[j] && graph[minNode][j] != INF) { // 更新未访问过的地点的最短距离
int newDist = dist[minNode] + graph[minNode][j];
if (newDist < dist[j]) {
dist[j] = newDist;
}
}
}
}
// 打印路径
printf("最短距离为:%d\n", dist[n-1]);
printf("最短路径为:");
int path[5];
int index = 0;
int node = n-1;
while (node != 0) { // 从终点往起点遍历
path[index++] = node;
for (int j = 0; j < n; j++) { // 找到能到达当前节点的上一个节点
if (graph[j][node] != INF && dist[node]-graph[j][node] == dist[j]) {
node = j;
break;
}
}
}
path[index++] = 0; // 加上起点
for (int i = index-1; i >= 0; i--) { // 倒序输出路径
printf("%c ", path[i]+'A');
}
printf("\n");
```
以上代码中的距离矩阵可以看成是一个有向加权图,每个地点是图中的节点,地点之间的距离是边的权重。算法的时间复杂度为O(n^2),其中n是地点数量。
阅读全文