校园地图有15个建筑23条路经,用迪杰斯特拉算法,输入1个建筑,输出这个建筑到另外14个建筑的最短路径,用C语言写代码
时间: 2024-03-22 14:37:05 浏览: 10
好的,以下是一个用 C 语言实现 Dijkstra 算法求解校园地图最短路径的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_VERTICES 15
#define MAX_EDGES 23
int distance[MAX_VERTICES]; // 存储起点到每个顶点的最短距离
int visited[MAX_VERTICES]; // 标记每个顶点是否已经确定最短路径
int graph[MAX_VERTICES][MAX_VERTICES]; // 存储图的边权重信息
// 初始化图
void init_graph() {
int i, j;
for (i = 0; i < MAX_VERTICES; i++) {
for (j = 0; j < MAX_VERTICES; j++) {
graph[i][j] = INT_MAX; // 初始化为无穷大
}
}
// 添加图的边
graph[0][1] = graph[1][0] = 4;
graph[0][2] = graph[2][0] = 1;
graph[0][3] = graph[3][0] = 3;
graph[1][4] = graph[4][1] = 6;
graph[2][4] = graph[4][2] = 4;
graph[2][5] = graph[5][2] = 2;
graph[3][5] = graph[5][3] = 3;
graph[4][6] = graph[6][4] = 5;
graph[4][7] = graph[7][4] = 2;
graph[5][7] = graph[7][5] = 7;
graph[5][8] = graph[8][5] = 3;
graph[6][9] = graph[9][6] = 2;
graph[7][9] = graph[9][7] = 3;
graph[7][10] = graph[10][7] = 2;
graph[8][10] = graph[10][8] = 4;
graph[9][11] = graph[11][9] = 4;
graph[10][11] = graph[11][10] = 5;
graph[10][12] = graph[12][10] = 1;
graph[11][13] = graph[13][11] = 6;
graph[12][13] = graph[13][12] = 5;
graph[12][14] = graph[14][12] = 3;
}
// 迪杰斯特拉算法函数
void dijkstra(int start) {
int i, j, min_dist, current;
// 初始化距离和访问数组
for (i = 0; i < MAX_VERTICES; i++) {
distance[i] = INT_MAX;
visited[i] = 0;
}
distance[start] = 0; // 起点到自己的距离为0
// 循环处理每个顶点
for (i = 0; i < MAX_VERTICES; i++) {
min_dist = INT_MAX;
// 选取距离起点最近的顶点
for (j = 0; j < MAX_VERTICES; j++) {
if (!visited[j] && distance[j] <= min_dist) {
min_dist = distance[j];
current = j;
}
}
// 标记当前顶点已经确定最短路径
visited[current] = 1;
// 更新从起点到其它顶点的距离
for (j = 0; j < MAX_VERTICES; j++) {
if (!visited[j] && graph[current][j] != INT_MAX && distance[current] + graph[current][j] < distance[j]) {
distance[j] = distance[current] + graph[current][j];
}
}
}
}
int main() {
init_graph(); // 初始化图
int i, start;
printf("请输入起点建筑编号(0-14):");
scanf("%d", &start);
dijkstra(start); // 调用迪杰斯特拉算法
printf("起点到每个建筑的最短路径如下:\n");
for (i = 0; i < MAX_VERTICES; i++) {
if (i != start) {
printf("建筑%d: %d\n", i, distance[i]);
}
}
return 0;
}
```
在上述代码中,我们使用了邻接矩阵来表示图的边权重信息。通过调用 `init_graph()` 函数进行初始化,然后读入起点建筑编号,调用 `dijkstra()` 函数求解最短路径,并输出结果。