C语言实现迪杰斯特拉算法求解交通咨询系统最短路径

以下是一个使用迪杰斯特拉算法求解给定带权有向图的最短路径的C语言代码示例：\n\nc\n#include \"stdio.h\"\n#include \"stdbool.h\"\n\n#define MAX_SIZE 100\n#define INFINITY 99999\n\n// 有向图的邻接矩阵表示\ntypedef struct {\n int vertexNum;\n int edgeNum;\n int adjacencyMatrix[MAX_SIZE][MAX_SIZE];\n} Graph;\n\n// 初始化有向图\nvoid initGraph(Graph *G, int vertexNum, int edgeNum) {\n G->vertexNum = vertexNum;\n G->edgeNum = edgeNum;\n int i, j;\n for (i = 0; i < vertexNum; i++) {\n for (j = 0; j < vertexNum; j++) {\n G->adjacencyMatrix[i][j] = INFINITY;\n }\n }\n}\n\n// 添加有向边\nvoid addEdge(Graph *G, int start, int end, int weight) {\n G->adjacencyMatrix[start][end] = weight;\n}\n\n// 打印最短路径\nvoid printShortestPath(int dist[], int parent[], int vertexNum, int source) {\n printf("Vertex\tDistance\tPath\n");\n int i;\n for (i = 0; i < vertexNum; i++) {\n if (i != source) {\n printf("%d\t%d\t\t", i, dist[i]);\n int j = i;\n while (j != source) {\n printf("%d <- ", j);\n j = parent[j];\n }\n printf("%d\n", source);\n }\n }\n}\n\n// 找到距离数组中最小距离的顶点\nint findMinDistanceVertex(int dist[], bool visited[], int vertexNum) {\n int minDistance = INFINITY;\n int minVertex;\n int i;\n for (i = 0; i < vertexNum; i++) {\n if (!visited[i] && dist[i] <= minDistance) {\n minDistance = dist[i];\n minVertex = i;\n }\n }\n return minVertex;\n}\n\n// 使用迪杰斯特拉算法找到源点到其他顶点的最短路径\nvoid dijkstra(Graph *G, int source) {\n int dist[MAX_SIZE];\n bool visited[MAX_SIZE];\n int parent[MAX_SIZE];\n int i;\n\n // 初始化距离数组、访问数组和父节点数组\n for (i = 0; i < G->vertexNum; i++) {\n dist[i] = INFINITY;\n visited[i] = false;\n parent[i] = -1;\n }\n\n // 设置源点的距离为0\n dist[source] = 0;\n\n // 寻找最短路径\n for (i = 0; i < G->vertexNum - 1; i++) {\n int u = findMinDistanceVertex(dist, visited, G->vertexNum);\n visited[u] = true;\n int v;\n for (v = 0; v < G->vertexNum; v++) {\n if (!visited[v] && G->adjacencyMatrix[u][v] != INFINITY && dist[u] + G->adjacencyMatrix[u][v] < dist[v]) {\n dist[v] = dist[u] + G->adjacencyMatrix[u][v];\n parent[v] = u;\n }\n }\n }\n\n // 打印最短路径\n printShortestPath(dist, parent, G->vertexNum, source);\n}\n\nint main() {\n Graph G;\n int vertexNum, edgeNum, source, start, end, weight;\n \n printf("Enter the number of vertices: ");\n scanf("%d", &vertexNum);\n printf("Enter the number of edges: ");\n scanf("%d", &edgeNum);\n\n initGraph(&G, vertexNum, edgeNum);\n\n printf("Enter the edges (start end weight):\n");\n int i;\n for (i = 0; i < edgeNum; i++) {\n scanf("%d %d %d", &start, &end, &weight);\n addEdge(&G, start, end, weight);\n }\n\n printf("Enter the source vertex: ");\n scanf("%d", &source);\n\n dijkstra(&G, source);\n\n return 0;\n}\n\n\n请注意，此代码示例仅给出了一个基本的实现。您可以根据实际需求对其进行修改和扩展。\n\n为了画出有向图，您可以使用图形库（如Graphviz）来生成图形表示。以下是一个使用Graphviz的示例代码：\n\nc\n#include \"stdio.h\"\n\n// 画出有向图\nvoid drawGraph(Graph *G) {\n FILE *dotFile = fopen("graph.dot", "w");\n fprintf(dotFile, "digraph G {\n");\n int i, j;\n for (i = 0; i < G->vertexNum; i++) {\n for (j = 0; j < G->vertexNum; j++) {\n if (G->adjacencyMatrix[i][j] != INFINITY) {\n fprintf(dotFile, "%d -> %d [label=%d];\n", i, j, G->adjacencyMatrix[i][j]);\n }\n }\n }\n fprintf(dotFile, "}");\n fclose(dotFile);\n system("dot -Tpng graph.dot -o graph.png"); // 生成PNG图片文件\n}\n\nint main() {\n // ...\n \n dijkstra(&G, source);\n \n drawGraph(&G);\n \n return 0;\n}\n\n\n运行代码后，将生成一个名为graph.png的PNG图片文件，表示给定有向图。