Dijkstra算法求解最短路径：校园地图导航

#include <stdio.h>\n#include <stdlib.h>\n#include <stdbool.h>\n\n#define MAX_SIZE 100\n#define INF 9999\n\n// 定义图的结构体\ntypedef struct {\n int matrix[MAX_SIZE][MAX_SIZE]; // 邻接矩阵表示图\n int vertexNum; // 顶点数量\n char* vertexNames[MAX_SIZE]; // 顶点名称\n} Graph;\n\n// 初始化图\nvoid initGraph(Graph* graph, int vertexNum) {\n graph->vertexNum = vertexNum;\n for (int i = 0; i < vertexNum; i++) {\n for (int j = 0; j < vertexNum; j++) {\n if (i == j) {\n graph->matrix[i][j] = 0;\n } else {\n graph->matrix[i][j] = INF;\n } \n }\n }\n}\n\n// 添加边\nvoid addEdge(Graph* graph, int start, int end, int weight) {\n graph->matrix[start][end] = weight;\n graph->matrix[end][start] = weight;\n}\n\n// 迪杰斯特拉算法\nvoid dijkstra(const Graph* graph, int start, int end) {\n int distance[MAX_SIZE]; // 存储起点到各点的最短距离\n bool visited[MAX_SIZE]; // 记录各个顶点是否已访问\n int path[MAX_SIZE]; // 存储最短路径的前驱节点\n\n // 初始化\n for (int i = 0; i < graph->vertexNum; i++) {\n distance[i] = graph->matrix[start][i];\n visited[i] = false;\n if (distance[i] < INF) {\n path[i] = start;\n } else {\n path[i] = -1;\n }\n }\n\n visited[start] = true;\n\n for (int i = 1; i < graph->vertexNum; i++) {\n int minDistance = INF;\n int minIndex = -1;\n\n // 找到未访问的顶点中距离起点最近的顶点\n for (int j = 0; j < graph->vertexNum; j++) {\n if (!visited[j] && distance[j] < minDistance) {\n minDistance = distance[j];\n minIndex = j;\n }\n }\n\n if (minIndex == -1) {\n break;\n }\n\n visited[minIndex] = true;\n\n // 更新最短距离和路径\n for (int j = 0; j < graph->vertexNum; j++) {\n if (!visited[j] && distance[minIndex] + graph->matrix[minIndex][j] < distance[j]) {\n distance[j] = distance[minIndex] + graph->matrix[minIndex][j];\n path[j] = minIndex;\n }\n }\n }\n\n // 输出最短路径和距离\n printf("最短路径为：");\n int currentNode = end;\n int pathStack[MAX_SIZE];\n int top = 0;\n while (currentNode != start) {\n pathStack[top++] = currentNode;\n currentNode = path[currentNode];\n }\n\n printf("%s", graph->vertexNames[start]);\n while (top > 0) {\n printf("->%s", graph->vertexNames[pathStack[--top]]);\n }\n printf("\n最短距离为：%d\n", distance[end]);\n}\n\nint main() {\n Graph graph;\n initGraph(&graph, 28);\n //定义顶点（地点）个数 \n\n // 添加边\n addEdge(&graph,0,1,25);\n addEdge(&graph,0,2,50);\n addEdge(&graph,2,3,100);\n addEdge(&graph,2,4,125);\n addEdge(&graph,3,4,75);\n addEdge(&graph,4,5,25);\n addEdge(&graph,5,6,50);\n addEdge(&graph,5,7,25);\n addEdge(&graph,5,9,50);\n addEdge(&graph,9,10,50);\n addEdge(&graph,7,10,50);\n addEdge(&graph,6,8,50);\n addEdge(&graph,9,8,100);\n addEdge(&graph,8,11,25);\n addEdge(&graph,11,12,50);\n addEdge(&graph,11,14,25);\n addEdge(&graph,12,13,25);\n addEdge(&graph,14,13,50);\n addEdge(&graph,14,16,75);\n addEdge(&graph,14,15,50);\n addEdge(&graph,13,16,25);\n addEdge(&graph,15,16,50);\n addEdge(&graph,15,17,75);\n addEdge(&graph,17,16,75);\n addEdge(&graph,9,20,75);\n addEdge(&graph,20,12,25);\n addEdge(&graph,20,23,25);\n addEdge(&graph,23,16,50);\n addEdge(&graph,16,24,50);\n addEdge(&graph,23,24,50);\n addEdge(&graph,9,18,50);\n addEdge(&graph,18,20,25);\n addEdge(&graph,20,21,25);\n addEdge(&graph,18,21,25);\n addEdge(&graph,10,18,50);\n addEdge(&graph,10,19,50);\n addEdge(&graph,18,19,25);\n addEdge(&graph,19,21,50);\n addEdge(&graph,19,22,25);\n addEdge(&graph,21,22,25);\n addEdge(&graph,21,25,25);\n addEdge(&graph,22,25,25);\n addEdge(&graph,25,26,25);\n addEdge(&graph,26,27,50);\n addEdge(&graph,24,27,50);\n addEdge(&graph,24,26,25);\n addEdge(&graph,21,24,50);\n\n graph.vertexNames[0] = "工商学院";\n graph.vertexNames[1] = "北区食堂";\n graph.vertexNames[2] = "三教";\n graph.vertexNames[3] = "北区篮球场";\n graph.vertexNames[4] = "7号门";\n graph.vertexNames[5] = "6号门";\n graph.vertexNames[6] = "静庐";\n graph.vertexNames[7] = "校医院"; \n graph.vertexNames[8] = "一食堂";\n graph.vertexNames[9] = "十二生肖广场";\n graph.vertexNames[10]= "二食堂";\n graph.vertexNames[11]= "宁庐";\n graph.vertexNames[12]= "大学生活动中心";\n graph.vertexNames[13]= "大礼堂";\n graph.vertexNames[14]= "南区篮球场";\n graph.vertexNames[15]= "萃庐";\n graph.vertexNames[16]= "一教";\n graph.vertexNames[17]= "荟庐";\n graph.vertexNames[18]= "和庐";\n graph.vertexNames[19]= "操场";\n graph.vertexNames[20]= "图书馆";\n graph.vertexNames[21]= "体育馆";\n graph.vertexNames[22]= "网球场";\n graph.vertexNames[23]= "至善广场";\n graph.vertexNames[24]= "二教";\n graph.vertexNames[25]= "足球场";\n graph.vertexNames[26]= "群庐";\n graph.vertexNames[27]= "英庐";\n\n int start, end;\n printf("0:工商学院\n 1:北区食堂\n 2:三教\n 3:北区篮球场\n 4:7号门\n 5:6号门\n 6:静庐\n 7:校医院\n 8:一食堂\n 9:十二生肖广场\n 10:二食堂\n 11:宁庐\n 12:大学生活动中心\n 13:大礼堂\n 14:南区篮球场\n 15:萃庐\n 16:\n 17:\n 18:\n 19:\n 20:\n 21:\n 22:\n 23:\n 24:\n 25:\n 26:\n 27:\n");\n printf("请输入起点和终点的编号（0-27）：");\n scanf("%d %d", &start, &end);\n\n dijkstra(&graph, start, end);\n\n return 0;\n