C语言实现Dijkstra算法和Prim算法求解最短路径和最小生成树

#include <stdio.h>\n#include <stdbool.h>\n#include <limits.h>\n#define MAX_CITIES 100\n\nint numCities, numRoads;\nint graph[MAX_CITIES][MAX_CITIES]; \n\nvoid initializeGraph(int n) {\n numCities = n;\n for (int i = 0; i < numCities; i++) {\n for (int j = 0; j < numCities; j++) {\n graph[i][j] = 0;\n }\n }\n}\n\nvoid addRoad(int city1, int city2, int distance) {\n graph[city1][city2] = distance;\n graph[city2][city1] = distance;\n}\n\nint findMinKey(int key[], bool mstSet[]) {\n int min = INT_MAX, min_index;\n\n for (int i = 0; i < numCities; i++) {\n if (mstSet[i] == false && key[i] < min) {\n min = key[i];\n min_index = i;\n }\n }\n\n return min_index;\n}\n\nvoid printMST(int parent[]) {\n printf("最小生成树的边：\n");\n for (int i = 1; i < numCities; i++) {\n printf("%d - %d\n", parent[i], i);\n }\n}\n\nvoid printShortestPath(int destination, int parent[]) {\n if (parent[destination] == -1) {\n printf("%d ", destination);\n return;\n }\n\n printShortestPath(parent[destination], parent);\n printf("-> %d ", destination);\n}\n\nvoid dijkstra(int startCity) {\n int distances[MAX_CITIES];\n bool visited[MAX_CITIES];\n int parent[MAX_CITIES];\n\n for (int i = 0; i < numCities; i++) { // 初始化\n distances[i] = INT_MAX;\n visited[i] = false;\n parent[i] = -1;\n }\n\n distances[startCity] = 0; // 设置起始城市的距离为0\n\n for (int count = 0; count < numCities - 1; count++) {\n int u = findMinKey(distances, visited); // 选择距离最小且未被标记的城市\n visited[u] = true;\n\n for (int v = 0; v < numCities; v++) {\n if (!visited[v] && graph[u][v] && distances[u] != INT_MAX && distances[u] + graph[u][v] < distances[v]) {\n distances[v] = distances[u] + graph[u][v];\n parent[v] = u;\n }\n }\n }\n\n printf("从起始城市到其他城市的最短路径：\n");\n for (int i = 0; i < numCities; i++) {\n if (i != startCity) {\n printf("从 %d 到 %d 的最短路径为：", startCity, i);\n printShortestPath(i, parent);\n printf("\n");\n }\n }\n}\n\nvoid primMST() {\n int parent[MAX_CITIES]; // 存储最小生成树的父节点\n int key[MAX_CITIES]; // 存储顶点与最小生成树之间的最小权值\n\n bool mstSet[MAX_CITIES]; // 用于标记顶点是否已包含在最小生成树中\n\n for (int i = 0; i < numCities; i++) {\n key[i] = INT_MAX;\n mstSet[i] = false;\n }\n\n key[0] = 0; // 选择第一个顶点作为起始顶点\n parent[0] = -1; // 第一个顶点没有父节点\n\n for (int count = 0; count < numCities - 1; count++) {\n int u = findMinKey(key, mstSet);\n mstSet[u] = true;\n\n for (int v = 0; v < numCities; v++) {\n if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) {\n parent[v] = u;\n key[v] = graph[u][v];\n }\n }\n }\n\n printMST(parent);\n}\n\nint main() {\n int i, city1, city2, distance;\n\n printf("请输入城市数量：");\n scanf("%d", &numCities);\n\n printf("请输入道路数量：");\n scanf("%d", &numRoads);\n\n initializeGraph(numCities);\n\n printf("请输入每条道路的起始城市、目标城市和距离：\n");\n for (i = 0; i < numRoads; i++) {\n printf("道路 %d：", i + 1);\n scanf("%d %d %d", &city1, &city2, &distance);\n addRoad(city1, city2, distance);\n }\n\n int startCity;\n printf("请输入起始城市：");\n scanf("%d", &startCity);\n\n dijkstra(startCity);\n primMST();\n\n return 0;\n