用C语言编写一个能求出学生在学校的一天最短路径的方法
时间: 2024-02-26 13:53:06 浏览: 47
好的,下面是一个用C语言编写的Dijkstra算法的示例来求解学生在学校内的最短路径。
```c
#include <stdio.h>
#include <limits.h>
#define V 9 // 学校内的节点数量
#define INF INT_MAX // 定义无穷大
// 从未处理的节点中查找距离源节点最近的节点
int minDistance(int dist[], bool sptSet[])
{
int min = INF;
int min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
// 打印最短路径的结果
void printSolution(int dist[], int n)
{
printf("节点 距离源节点的距离\n");
for (int i = 0; i < V; i++)
printf("%d\t%d\n", i, dist[i]);
}
// Dijkstra算法
void dijkstra(int graph[V][V], int src)
{
int dist[V]; // 存储每个节点到源节点的距离
bool sptSet[V]; // 标记节点是否被处理
// 初始化所有节点的距离为无穷大,标记为未处理
for (int i = 0; i < V; i++)
dist[i] = INF, sptSet[i] = false;
// 源节点的距离为0
dist[src] = 0;
// 处理所有节点
for (int count = 0; count < V - 1; count++) {
// 从未处理的节点中查找距离源节点最近的节点
int u = minDistance(dist, sptSet);
// 标记这个节点已经被处理
sptSet[u] = true;
// 更新所有与该节点相邻的节点的距离
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v] && dist[u] != INF && dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
// 打印最短路径的结果
printSolution(dist, V);
}
// 主函数
int main()
{
// 定义学校内的图
int graph[V][V] = {
{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
// 从节点0开始计算最短路径
dijkstra(graph, 0);
return 0;
}
```
这个例子中,我们假设学校内有9个节点,通过一个邻接矩阵定义了这些节点之间的连接关系。其中,0表示两个节点之间没有连接,其他数字表示两个节点之间的距离。运行程序后,输出的结果将会显示每个节点到源节点的最短距离。
阅读全文