最小生成树和最短路径算法：城市网络路径规划

{/'title/':/'//(3//) 图的应用//(最小生成树和最短路径//)：/',/'description/':/'假设有一个城市网络，其中包含n个城市和m条道路。每条道路都连接两个城市，并且具有一个非负的距离值。我们需要找到从给定起始城市到其他所有城市的最短路径和最小生成树。/',/'keywords/':/'最小生成树, 最短路径, 图算法, Prim算法, Dijkstra算法, 城市网络, 路径规划/',/'content/':/'#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;//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}/