校园地图上有工科楼、实训楼、实验楼、图书馆、南门、教学楼A、教学楼B、音乐厅、逸夫楼、篮球场、体育场、美术厅、第一食堂、第二食堂、北门15个建筑,这十五个点之间的距离关系用领接矩阵可表示为{0 175 101 ∞ 150 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞} {175 0 107 65 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞} {101 107 0 127 63 80 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞} {∞ 65 127 0 170 139 ∞ 253 ∞ ∞ ∞ ∞ ∞ ∞ ∞} {150 ∞ 63 170 0 93 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞} {∞ ∞ 80 139 93 0 45 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞} {∞ ∞ ∞ ∞ ∞ 45 0 ∞ 62 ∞ ∞ ∞ ∞ ∞ ∞} {∞ ∞ ∞ 235 ∞ ∞ ∞ 0 ∞ 238 ∞ 90 ∞ ∞ ∞} {∞ ∞ ∞ ∞ ∞ ∞ 62 ∞ 0 194 99 ∞ ∞ 271 ∞} {∞ ∞ ∞ ∞ ∞ ∞ ∞ 238 194 0 ∞ ∞ ∞ ∞ ∞} {∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 99 ∞ 0 ∞ ∞ ∞ 69} {∞ ∞ ∞ ∞ ∞ ∞ ∞ 90 ∞ ∞ ∞ 0 315 ∞ ∞} {∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 315 0 55 ∞} {∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 271 ∞ ∞ ∞ 55 0 223} {∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 69 ∞ ∞ 223 0}用迪杰斯特拉算法与c语言写出一个程序,完成输入一个建筑就能输出这个建筑到其余各建筑的最短路径与距离。
时间: 2024-02-10 20:15:26 浏览: 16
以下是基于邻接矩阵和迪杰斯特拉算法的C语言代码实现:
```
#include <stdio.h>
#define INF 0x3f3f3f3f // 无穷大
void dijkstra(int graph[15][15], int start) {
int dist[15]; // 存储起点到各个点的距离
int visited[15] = {0}; // 标记已经访问的点
int i, j, min_idx, min_dist;
// 初始化dist数组
for (i = 0; i < 15; i++) {
dist[i] = graph[start][i];
}
visited[start] = 1;
// 执行n-1次循环,每次确定一个点的最短路径
for (i = 0; i < 14; i++) {
min_dist = INF;
// 找到未访问的距离起点最近的点
for (j = 0; j < 15; j++) {
if (!visited[j] && dist[j] < min_dist) {
min_dist = dist[j];
min_idx = j;
}
}
visited[min_idx] = 1;
// 更新起点到其他点的距离
for (j = 0; j < 15; j++) {
if (!visited[j] && graph[min_idx][j] != INF && dist[min_idx] + graph[min_idx][j] < dist[j]) {
dist[j] = dist[min_idx] + graph[min_idx][j];
}
}
}
// 输出结果
for (i = 0; i < 15; i++) {
if (i != start) {
printf("%c -> %c: %d\n", (char)(start+'A'), (char)(i+'A'), dist[i]);
}
}
}
int main() {
int graph[15][15] = {{0, 175, 101, INF, 150, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
{175, 0, 107, 65, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
{101, 107, 0, 127, 63, 80, INF, INF, INF, INF, INF, INF, INF, INF, INF},
{INF, 65, 127, 0, 170, 139, INF, 253, INF, INF, INF, INF, INF, INF, INF},
{150, INF, 63, 170, 0, 93, INF, INF, INF, INF, INF, INF, INF, INF, INF},
{INF, INF, 80, 139, 93, 0, 45, INF, INF, INF, INF, INF, INF, INF, INF},
{INF, INF, INF, INF, INF, 45, 0, INF, 62, INF, INF, INF, INF, INF, INF},
{INF, INF, INF, 235, INF, INF, INF, 0, INF, 238, INF, 90, INF, INF, INF},
{INF, INF, INF, INF, INF, INF, 62, INF, 0, 194, 99, INF, INF, 271, INF},
{INF, INF, INF, INF, INF, INF, INF, 238, 194, 0, INF, INF, INF, INF, INF},
{INF, INF, INF, INF, INF, INF, INF, INF, 99, INF, 0, INF, INF, 69, INF},
{INF, INF, INF, INF, INF, INF, INF, 90, INF, INF, INF, 0, 315, INF, INF},
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 315, 0, 55, INF},
{INF, INF, INF, INF, INF, INF, INF, INF, 271, INF, 69, INF, 55, 0, 223},
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 223, 0}};
int start;
char building;
printf("请输入起点建筑(大写字母A-O):");
scanf("%c", &building);
start = building - 'A';
dijkstra(graph, start);
return 0;
}
```
程序会提示用户输入起点建筑的大写字母,然后利用迪杰斯特拉算法计算起点到各个点的最短路径,并输出结果。注意,程序中的邻接矩阵中,用INF表示两个建筑之间没有直接的路径。