C语言实现迪杰斯特拉算法求最短路径 - 图的遍历与应用

"#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// 添加边\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 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 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 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 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, 9);\n\n // 添加边\n addEdge(&graph, 0, 1, 1);\n addEdge(&graph, 1, 4, 2);\n addEdge(&graph, 1, 3, 3);\n addEdge(&graph, 1, 2, 3);\n addEdge(&graph, 2, 5, 1);\n addEdge(&graph, 2, 6, 1);\n addEdge(&graph, 4, 7, 1);\n addEdge(&graph, 3, 5, 2);\n addEdge(&graph, 3, 8, 4);\n addEdge(&graph, 7, 8, 2);\n addEdge(&graph, 6, 8, 1);\n addEdge(&graph, 5, 8, 1);\n addEdge(&graph, 2, 8, 2);\n addEdge(&graph, 6, 7, 1);\n\n graph.vertexNames[0] = "6号门";\n graph.vertexNames[1] = "十二生肖广场";\n graph.vertexNames[2] = "图文楼";\n graph.vertexNames[3] = "一食堂";\n graph.vertexNames[4] = "二食堂";\n graph.vertexNames[5] = "大学生活动中心";\n graph.vertexNames[6] = "体育馆";\n graph.vertexNames[7] = "操场";\n\n int start, end;\n printf("请输入起点和终点的编号（0-8）：");\n scanf("%d %d", &start, &end);\n\n dijkstra(&graph, start, end);\n\n return 0;\n}\n\n代码中顶点和边的数量是哪段内容：顶点数量是9，边的数量是14。