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}\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, 9);\n\n // 添加边\n addEdge(&graph, 0, 1, 1);\n addEdge(&graph, 0, 2, 3);\n addEdge(&graph, 1, 3, 5);\n addEdge(&graph, 1, 4, 6);\n addEdge(&graph, 2, 3, 2);\n addEdge(&graph, 2, 5, 7);\n addEdge(&graph, 3, 4, 3);\n addEdge(&graph, 3, 6, 9);\n addEdge(&graph, 4, 6, 2);\n addEdge(&graph, 4, 7, 7);\n addEdge(&graph, 5, 6, 4);\n addEdge(&graph, 5, 8, 6);\n addEdge(&graph, 6, 7, 5);\n addEdge(&graph, 7, 8, 3);\n\n graph.vertexNames[0] = "A";\n graph.vertexNames[1] = "B";\n graph.vertexNames[2] = "C";\n graph.vertexNames[3] = "D";\n graph.vertexNames[4] = "E";\n graph.vertexNames[5] = "F";\n graph.vertexNames[6] = "G";\n graph.vertexNames[7] = "H";\n graph.vertexNames[8] = "I";\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