运用数据结构知识编写一个校园以江西财经大学麦庐园为例导航的C语言代码要求运用迪杰斯特拉算法求最短路径。
以下是一个使用迪杰斯特拉算法求最短路径的校园导航的C语言代码示例:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_VERTICES 100
#define INFINITY 99999
typedef struct {
int weight;
bool visited;
int prev;
} Vertex;
int graph[MAX_VERTICES][MAX_VERTICES];
Vertex vertices[MAX_VERTICES];
int numVertices;
// 初始化图
void initGraph() {
int i, j;
for (i = 0; i < MAX_VERTICES; i++) {
for (j = 0; j < MAX_VERTICES; j++) {
graph[i][j] = (i == j) ? 0 : INFINITY;
}
}
}
// 添加边
void addEdge(int start, int end, int weight) {
graph[start][end] = weight;
graph[end][start] = weight;
}
// 寻找最短路径
void dijkstra(int start) {
int i, j, minIndex, minDist;
// 初始化顶点信息
for (i = 0; i < numVertices; i++) {
vertices[i].weight = INFINITY;
vertices[i].visited = false;
vertices[i].prev = -1;
}
vertices[start].weight = 0;
for (i = 0; i < numVertices; i++) {
minIndex = -1;
minDist = INFINITY;
// 找到未访问的最近顶点
for (j = 0; j < numVertices; j++) {
if (!vertices[j].visited && vertices[j].weight < minDist) {
minIndex = j;
minDist = vertices[j].weight;
}
}
if (minIndex == -1) {
break;
}
vertices[minIndex].visited = true;
// 更新与最近顶点相邻的顶点的权值
for (j = 0; j < numVertices; j++) {
if (!vertices[j].visited && graph[minIndex][j] != INFINITY) {
int newDist = vertices[minIndex].weight + graph[minIndex][j];
if (newDist < vertices[j].weight) {
vertices[j].weight = newDist;
vertices[j].prev = minIndex;
}
}
}
}
}
// 打印最短路径
void printShortestPath(int start, int end) {
int path[MAX_VERTICES];
int pathLength = 0;
int i = end;
while (i != start) {
path[pathLength++] = i;
i = vertices[i].prev;
}
printf("最短路径为:");
printf("%d", start);
for (i = pathLength - 1; i >= 0; i--) {
printf(" -> %d", path[i]);
}
printf("\n");
}
int main() {
initGraph();
// 添加校园地点和路径信息
numVertices = 8;
addEdge(0, 1, 5);
addEdge(0, 2, 10);
addEdge(1, 3, 8);
addEdge(1, 4, 4);
addEdge(2, 3, 3);
addEdge(2, 5, 6);
addEdge(3, 4, 7);
addEdge(3, 5, 2);
addEdge(4, 6, 5);
addEdge(5, 6, 9);
addEdge(5, 7, 1);
addEdge(6, 7, 12);
dijkstra(0);
printShortestPath(0, 7);
return 0;
}
上述代码中,我们通过定义一个二维数组来表示校园地点之间的路径,并使用迪杰斯特拉算法来计算最短路径。initGraph()函数用于初始化图,addEdge()函数用于添加边,dijkstra()函数用于寻找最短路径,printShortestPath()函数用于打印最短路径。
在main()函数中,我们通过添加校园地点和路径信息来构建图,并调用dijkstra()函数来计算最短路径,最后调用printShortestPath()函数来打印最短路径。
请注意,上述代码只是一个示例,具体的校园地点和路径信息需要根据实际情况进行修改
原文地址: https://www.cveoy.top/t/topic/h0PS 著作权归作者所有。请勿转载和采集!