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

本程序使用C语言实现Dijkstra算法和Prim算法，分别用于求解单源最短路径和最小生成树问题。程序首先读取用户输入的城市数量和道路信息，构建图形，然后使用Dijkstra算法计算从起始城市到其他城市的最短路径，最后使用Prim算法求解最小生成树。

代码实现

#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#define MAX_CITIES 100
int numCities, numRoads;
int graph[MAX_CITIES][MAX_CITIES];
void initializeGraph(int n) {
numCities = n;
for (int i = 0; i < numCities; i++) {
for (int j = 0; j < numCities; j++) {
graph[i][j] = 0;
}
}
}
void addRoad(int city1, int city2, int distance) {
graph[city1][city2] = distance;
graph[city2][city1] = distance;
}
int findMinKey(int key[], bool mstSet[]) {
int min = INT_MAX, min_index;
for (int i = 0; i &lt; numCities; i++) {
    if (mstSet[i] == false &amp;&amp; key[i] &lt; min) {
        min = key[i];
        min_index = i;
    }
}

return min_index;

}
void printMST(int parent[]) {
printf("最小生成树的边：\n");
for (int i = 1; i < numCities; i++) {
printf("%d - %d\n", parent[i], i);
}
}
void printShortestPath(int destination, int parent[]) {
if (parent[destination] == -1) {
printf("%d ", destination);
return;
}
printShortestPath(parent[destination], parent);
printf("-> %d ", destination);

}
void dijkstra(int startCity) {
int distances[MAX_CITIES];
bool visited[MAX_CITIES];
int parent[MAX_CITIES];
for (int i = 0; i &lt; numCities; i++) {
    distances[i] = INT_MAX;
    visited[i] = false;
    parent[i] = -1;
}

distances[startCity] = 0;

for (int count = 0; count &lt; numCities - 1; count++) {
    int u = findMinKey(distances, visited);
    visited[u] = true;

    for (int v = 0; v &lt; numCities; v++) {
        if (!visited[v] &amp;&amp; graph[u][v] &amp;&amp; distances[u] != INT_MAX &amp;&amp; distances[u] + graph[u][v] &lt; distances[v]) {
            distances[v] = distances[u] + graph[u][v];
            parent[v] = u;
        }
    }
}

printf("从起始城市到其他城市的最短路径：\n");
for (int i = 0; i &lt; numCities; i++) {
    if (i != startCity) {
        printf("从 %d 到 %d 的最短路径为：", startCity, i);
        printShortestPath(i, parent);
        printf("\n");
    }
}

}
void primMST() {
int parent[MAX_CITIES];
int key[MAX_CITIES];
bool mstSet[MAX_CITIES];

for (int i = 0; i &lt; numCities; i++) {
    key[i] = INT_MAX;
    mstSet[i] = false;
}

key[0] = 0;
parent[0] = -1; 

for (int count = 0; count &lt; numCities - 1; count++) {
    int u = findMinKey(key, mstSet);
    mstSet[u] = true;

    for (int v = 0; v &lt; numCities; v++) {
        if (graph[u][v] &amp;&amp; mstSet[v] == false &amp;&amp; graph[u][v] &lt; key[v]) {
            parent[v] = u;
            key[v] = graph[u][v];
        }
    }
}

printMST(parent);

}
int main() {
int i, city1, city2, distance;
printf("请输入城市数量：");
scanf("%d", &amp;numCities);

printf("请输入道路数量：");
scanf("%d", &amp;numRoads);

initializeGraph(numCities);

printf("请输入每条道路的起始城市、目标城市和距离：\n");
for (i = 0; i &lt; numRoads; i++) {
    printf("道路 %d：", i + 1);
    scanf("%d %d %d", &amp;city1, &amp;city2, &amp;distance);
    addRoad(city1, city2, distance);
}

int startCity;
printf("请输入起始城市：");
scanf("%d", &amp;startCity);

dijkstra(startCity);
primMST();

return 0;

}

答辩内容

这是一个使用Dijkstra算法和Prim算法实现最短路径和最小生成树的程序。程序首先读取用户输入的城市数量和道路数量，然后根据用户输入的道路信息构建图形。接下来，程序要求用户输入起始城市，并使用Dijkstra算法找到从起始城市到其他城市的最短路径。最后，程序使用Prim算法找到图形的最小生成树并打印出来。

在答辩时，你可以解释算法的原理和代码的工作方式。你可以提到Dijkstra算法是一种贪婪算法，用于解决单源最短路径问题。它使用一个距离数组来存储从起始城市到每个城市的最短距离，并使用一个访问数组来标记已经访问过的城市。每次选择距离数组中最小值对应的城市作为下一个访问的城市，并更新距离数组和访问数组。最终，距离数组中的值就是从起始城市到其他城市的最短路径长度。

你还可以解释Prim算法是一种贪婪算法，用于解决最小生成树问题。它从一个初始城市开始，每次选择一个连接已经选择的城市和未选择的城市的边中权重最小的边，并将未选择的城市添加到最小生成树中。最终，所有的城市都会被选择，并且最小生成树的边权重之和达到最小。

你可以演示程序的运行结果，并回答任何与算法和代码相关的问题。如果可能的话，你可以尝试提供一些改进或优化的建议。</p