选择20个城市,城市之间的距离作为边的权重值,用c语言设计一个简单的交通咨询系统,要求输入起点和终点,算法能给出最优路线。
时间: 2024-02-11 21:10:03 浏览: 24
这是一个经典的最短路径问题,可以使用Dijkstra算法或者Floyd算法来解决。以下是使用Dijkstra算法的具体步骤:
1. 定义一个二维数组dist,记录起点到各个点的最短距离,初始化为无穷大。
2. 定义一个一维数组visited,记录各个点是否已经被访问过,初始化为false。
3. 将起点的dist值初始化为0。
4. 从起点开始,遍历与起点相邻的所有点,更新它们的dist值。
5. 在未访问的点中,找到dist值最小的点,将其标记为已访问。
6. 重复步骤4和步骤5,直到终点被标记为已访问,或者所有点都被标记为已访问。
7. 最终,起点到终点的最短距离即为dist[终点],可以通过记录每个点的前驱节点,从终点回溯到起点,得到最短路径。
以下是C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_CITY 20
#define INF 1000000000
int dist[MAX_CITY][MAX_CITY]; // 二维数组dist,记录起点到各个点的最短距离
int visited[MAX_CITY]; // 一维数组visited,记录各个点是否已经被访问过
void dijkstra(int start, int end)
{
int i, j, u, min_dist;
// 初始化
for (i = 0; i < MAX_CITY; i++) {
visited[i] = 0;
dist[start][i] = dist[i][start] = INF;
}
visited[start] = 1;
dist[start][start] = 0;
// 更新与起点相邻的点的dist值
for (i = 0; i < MAX_CITY; i++) {
if (dist[start][i] != INF) {
dist[start][i] = dist[i][start] = dist[start][i];
}
}
// Dijkstra算法主循环
for (i = 1; i < MAX_CITY; i++) {
min_dist = INF;
for (j = 0; j < MAX_CITY; j++) {
if (!visited[j] && dist[start][j] < min_dist) {
u = j;
min_dist = dist[start][j];
}
}
visited[u] = 1;
if (u == end) {
break;
}
for (j = 0; j < MAX_CITY; j++) {
if (!visited[j] && dist[start][u] + dist[u][j] < dist[start][j]) {
dist[start][j] = dist[j][start] = dist[start][u] + dist[u][j];
}
}
}
// 输出最短距离和路径
printf("最短距离为:%d\n", dist[start][end]);
printf("最短路径为:");
i = end;
while (i != start) {
printf("%d<-", i);
for (j = 0; j < MAX_CITY; j++) {
if (dist[start][j] + dist[j][i] == dist[start][i]) {
i = j;
break;
}
}
}
printf("%d\n", start);
}
int main()
{
// 初始化距离
memset(dist, INF, sizeof(dist));
dist[0][1] = dist[1][0] = 1;
dist[0][3] = dist[3][0] = 3;
dist[0][4] = dist[4][0] = 2;
dist[1][2] = dist[2][1] = 2;
dist[1][3] = dist[3][1] = 4;
dist[1][4] = dist[4][1] = 3;
dist[2][4] = dist[4][2] = 5;
dist[2][5] = dist[5][2] = 6;
dist[3][4] = dist[4][3] = 1;
dist[3][6] = dist[6][3] = 10;
dist[4][5] = dist[5][4] = 8;
dist[4][6] = dist[6][4] = 6;
dist[4][7] = dist[7][4] = 7;
dist[5][7] = dist[7][5] = 9;
dist[5][8] = dist[8][5] = 3;
dist[6][7] = dist[7][6] = 5;
dist[6][9] = dist[9][6] = 2;
dist[7][8] = dist[8][7] = 4;
dist[7][9] = dist[9][7] = 6;
dist[8][9] = dist[9][8] = 1;
int start, end;
printf("请输入起点和终点(0-19):");
scanf("%d%d", &start, &end);
dijkstra(start, end);
return 0;
}
```