问题描述 一张地图包括 n 个城市，假设城市间有 m 条路径(有向图)，每条路径的长度已知。给定地图的一个起点城市和终点城市，利用 Diisktra算法求出起点到终点之间的最短路径。 输出要求 多组数据，每组数据有 m+3行。第一行为两个整数n和m分别代表城市个数和路径条数m。第二行有n个字符，代表每个城市的名字。第三行到第m+2行每行有两个字符a和b和一个整数 d，代表从城市a到城市b有一条距离为d的路。最后一行为两个字符，代表待求最短路径的城市起点和终点。当n和m都等于0时，输人结束。 输出要求 每组数据输出2行。第1行为一个整数，为从起点到终点之间最短路的长度。第 2行为一串字符串，代表该路径。每两个字符之间用空格隔开。 使用c语言，写出完整代码和注释，并针对核心算法函数分析时间和空间复杂度

以下是使用 Dijkstra 算法求解最短路径的 C 语言代码，附有详细注释： ```c #include <stdio.h> #include <string.h> #include <limits.h> #define MAXN 1005 // 最大城市数 #define MAXM 50005 // 最大路径数 #define INF 0x3f3f3f3f // 无穷大 int n, m; // 城市数和路径数 int dis[MAXN]; // 存储起点到每个城市的最短距离 int vis[MAXN]; // 标记每个城市是否已经被访问 int pre[MAXN]; // 存储每个城市在最短路径中的前一个城市 int edge[MAXM][3]; // 存储每条路径的起点、终点和长度 char name[MAXN][10]; // 存储每个城市的名称 char start[10], end[10]; // 起点和终点的名称 int dijkstra(int s, int t) { // 初始化 memset(dis, 0x3f, sizeof(dis)); memset(vis, 0, sizeof(vis)); memset(pre, -1, sizeof(pre)); dis[s] = 0; // 循环 n 次，每次选出一个未访问城市中距离最小的城市 for (int i = 0; i < n; ++i) { int x = -1; for (int j = 1; j <= n; ++j) { if (!vis[j] && (x == -1 || dis[j] < dis[x])) { x = j; } } if (x == -1) { break; } vis[x] = 1; // 更新与 x 相邻的城市的最短距离 for (int j = 0; j < m; ++j) { if (edge[j][0] == x) { int y = edge[j][1]; int w = edge[j][2]; if (dis[x] + w < dis[y]) { dis[y] = dis[x] + w; pre[y] = x; } } } } // 返回起点到终点的最短距离 return dis[t]; } void print_path(int s, int t) { int path[MAXN], cnt = 0; for (int i = t; i != -1; i = pre[i]) { path[cnt++] = i; } for (int i = cnt - 1; i >= 0; --i) { printf("%s", name[path[i]]); if (i > 0) { printf(" "); } } printf("\n"); } int main() { while (scanf("%d%d", &n, &m) == 2 && n != 0 && m != 0) { // 读入城市名称 for (int i = 1; i <= n; ++i) { scanf("%s", name[i]); } // 读入路径信息 for (int i = 0; i < m; ++i) { char a[10], b[10]; int d; scanf("%s%s%d", a, b, &d); int x, y; for (int j = 1; j <= n; ++j) { if (strcmp(name[j], a) == 0) { x = j; } if (strcmp(name[j], b) == 0) { y = j; } } edge[i][0] = x; edge[i][1] = y; edge[i][2] = d; } // 读入起点和终点 scanf("%s%s", start, end); int s, t; for (int i = 1; i <= n; ++i) { if (strcmp(name[i], start) == 0) { s = i; } if (strcmp(name[i], end) == 0) { t = i; } } // 求解最短路径并输出结果 int ans = dijkstra(s, t); if (ans < INF) { printf("%d\n", ans); print_path(s, t); } else { printf("Sorry, no path is found.\n"); } } return 0; } ``` 时间复杂度分析： Dijkstra 算法的时间复杂度为 O(n^2)，其中 n 为城市数。每次循环需要遍历 n 个城市找到距离起点最近的未访问城市，共循环 n 次，因此总时间复杂度为 O(n^2)。 空间复杂度分析： 空间复杂度主要取决于存储数据的数组大小，其中最大的数组是 edge 数组，其大小为 m * 3，因此空间复杂度为 O(m)。