C语言实现迪杰斯特拉算法求解最短路径

#include <stdio.h>\n#include <limits.h>\n\n#define MAX_VERTICES 100\n\n// \u4f7f\u7528\u4e8e\u8868\u793a\u56fe\u4e2d\u7684\u4e00\u5f20\u8fb9\ntypedef struct {\n int weight; // \u8fb9\u7684\u6743\u91cd\n int source; // \u8fb9\u7684\u5f00\u59cb\u70b9\n int target; // \u8fb9\u7684\u76ee\u6807\u70b9\n} Edge;\n\n// \u4f7f\u7528\u4e8e\u8868\u793a\u56fe\ntypedef struct {\n int numVertices; // \u56fe\u4e2d\u9876\u70b9\u7684\u6570\u91cf\n int numEdges; // \u56fe\u4e2d\u8fb9\u7684\u6570\u91cf\n int sourceVertex; // \u6e90\u70b9\n Edge edges[MAX_VERTICES]; // \u56fe\u4e2d\u7684\u8fb9\n int distance[MAX_VERTICES]; // \u6e90\u70b9\u5230\u5404\u70b9\u7684\u6700\u77ed\u8ddd\u79bb\n int previous[MAX_VERTICES]; // \u524d\u5904\u9876\u70b9\u6570\u7ec4\uff0c\u8bb0\u5f55\u6700\u77ed\u8def\u5f84\u4e0a\u6bcf\u4e2a\u9876\u70b9\u7684\u524d\u5904\u9876\u70b9\n} Graph;\n\n// \u521d\u59cb\u5316\u56fe\nvoid initGraph(Graph* graph, int numVertices, int numEdges, int sourceVertex) {\n graph->numVertices = numVertices;\n graph->numEdges = numEdges;\n graph->sourceVertex = sourceVertex;\n\n // \u521d\u59cb\u5316\u6700\u77ed\u8ddd\u79bb\u6570\u7ec4\u548c\u524d\u5904\u9876\u70b9\u6570\u7ec4\n for (int i = 0; i < numVertices; i++) {\n graph->distance[i] = INT_MAX;\n graph->previous[i] = -1;\n }\n}\n\n// \u6dfb\u52a0\u4e00\u5f20\u8fb9\u5230\u56fe\u4e2d\nvoid addEdge(Graph* graph, int source, int target, int weight) {\n graph->edges[graph->numEdges].source = source;\n graph->edges[graph->numEdges].target = target;\n graph->edges[graph->numEdges].weight = weight;\n graph->numEdges++;\n}\n\n// \u6267\u884c\u8c03\u5c14\u65af\u7279\u7b97\u6cd5\nvoid dijkstra(Graph* graph) {\n int numVertices = graph->numVertices;\n int numEdges = graph->numEdges;\n int sourceVertex = graph->sourceVertex;\n int* distance = graph->distance;\n int* previous = graph->previous;\n\n // \u521d\u59cb\u5316\u6e90\u70b9\u5230\u6e90\u70b9\u7684\u6700\u77ed\u8ddd\u79bb\u4e3a\u201c0\u201d\n distance[sourceVertex] = 0;\n\n // \u904d\u5386\u6240\u6709\u9876\u70b9\n for (int i = 0; i < numVertices - 1; i++) {\n // \u627e\u5230\u5f53\u524d\u672a\u8bbf\u95ee\u7684\u6700\u8fd1\u9876\u70b9\n int minDistance = INT_MAX;\n int minVertex = -1;\n\n for (int j = 0; j < numVertices; j++) {\n if (distance[j] < minDistance && previous[j] == -1) {\n minDistance = distance[j];\n minVertex = j;\n }\n }\n\n // \u6807\u8bb0\u5f53\u524d\u9876\u70b9\u4e3a\u5df2\u8bbf\u95ee\n previous[minVertex] = 1;\n\n // \u66f4\u65b0\u5f53\u524d\u9876\u70b9\u7684\u90bb\u63a5\u9876\u70b9\u7684\u6700\u77ed\u8ddd\u79bb\n for (int j = 0; j < numEdges; j++) {\n int source = graph->edges[j].source;\n int target = graph->edges[j].target;\n int weight = graph->edges[j].weight;\n\n if (source == minVertex && previous[target] == -1 && distance[source] + weight < distance[target]) {\n distance[target] = distance[source] + weight;\n previous[target] = source;\n }\n }\n }\n}\n\n// \u6253\u5370\u4ece\u6e90\u70b9\u5230\u5404\u70b9\u7684\u6700\u77ed\u8def\u5f84\nvoid printShortestPaths(Graph* graph) {\n int numVertices = graph->numVertices;\n int* distance = graph->distance;\n int* previous = graph->previous;\n\n printf("Shortest paths from vertex %d:\n", graph->sourceVertex);\n\n for (int i = 0; i < numVertices; i++) {\n printf("Vertex %d: ", i);\n\n if (distance[i] == INT_MAX) {\n printf("No path\n");\n } else {\n printf("%d ", distance[i]);\n\n int path[MAX_VERTICES];\n int pathLength = 0;\n int currentVertex = i;\n\n // \u6784\u5efa\u6700\u77ed\u8def\u5f84\n while (currentVertex != -1) {\n path[pathLength++] = currentVertex;\n currentVertex = previous[currentVertex];\n }\n\n // \u6253\u5370\u6700\u77ed\u8def\u5f84\n for (int j = pathLength - 1; j >= 0; j--) {\n printf("%d ", path[j]);\n }\n\n printf("\n");\n }\n }\n}\n\nint main() {\n Graph graph;\n int numVertices, numEdges, sourceVertex;\n int source, target, weight;\n\n printf("Enter the number of vertices in the graph: ");\n scanf("%d", &numVertices);\n\n printf("Enter the number of edges in the graph: ");\n scanf("%d", &numEdges);\n\n printf("Enter the source vertex: ");\n scanf("%d", &sourceVertex);\n\n initGraph(&graph, numVertices, numEdges, sourceVertex);\n\n printf("Enter the edges of the graph (source, target, weight):\n");\n for (int i = 0; i < numEdges; i++) {\n scanf("%d %d %d", &source, &target, &weight);\n addEdge(&graph, source, target, weight);\n }\n\n dijkstra(&graph);\n printShortestPaths(&graph);\n\n return 0;\n