C语言实现迪杰斯特拉算法求解最短路径 - 代码示例

#include <stdio.h>\n#include <stdbool.h>\n\n#define MAX_SIZE 100\n#define INF 9999\n\n// 有向图的邻接矩阵表示\ntypedef struct {\n int vertices[MAX_SIZE]; // 顶点集合\n int edges[MAX_SIZE][MAX_SIZE]; // 边的权重\n int vertexCount; // 顶点数量\n int edgeCount; // 边的数量\n} Graph;\n\n// 初始化有向图\nvoid initGraph(Graph* graph, int vCount, int eCount) {\n graph->vertexCount = vCount;\n graph->edgeCount = eCount;\n \n // 初始化边的权重为无穷大\n for (int i = 0; i < vCount; i++) {\n graph->vertices[i] = i;\n for (int j = 0; j < vCount; j++) {\n graph->edges[i][j] = INF;\n }\n }\n}\n\n// 添加有向边\nvoid addEdge(Graph* graph, int start, int end, int weight) {\n graph->edges[start][end] = weight;\n}\n\n// 打印最短路径\nvoid printShortestPaths(int dist[], int n) {\n printf("顶点\t最短距离\n");\n for (int i = 0; i < n; i++) {\n printf("%d\t%d\n", i, dist[i]);\n }\n}\n\n// 获取未访问顶点中距离最小的顶点\nint getMinDistanceVertex(int dist[], bool visited[], int n) {\n int minDist = INF;\n int minVertex = -1;\n \n for (int i = 0; i < n; i++) {\n if (!visited[i] && dist[i] < minDist) {\n minDist = dist[i];\n minVertex = i;\n }\n }\n \n return minVertex;\n}\n\n// 迪杰斯特拉算法求最短路径\nvoid dijkstra(Graph* graph, int start) {\n int dist[MAX_SIZE]; // 存储最短距离\n bool visited[MAX_SIZE]; // 记录顶点是否被访问\n int n = graph->vertexCount;\n \n // 初始化\n for (int i = 0; i < n; i++) {\n dist[i] = INF;\n visited[i] = false;\n }\n dist[start] = 0;\n \n for (int i = 0; i < n - 1; i++) {\n int u = getMinDistanceVertex(dist, visited, n);\n visited[u] = true;\n \n for (int v = 0; v < n; v++) {\n if (!visited[v] && graph->edges[u][v] != INF && dist[u] + graph->edges[u][v] < dist[v]) {\n dist[v] = dist[u] + graph->edges[u][v];\n }\n }\n }\n \n printShortestPaths(dist, n);\n}\n\nint main() {\n Graph graph;\n int vCount, eCount, start;\n \n printf("请输入顶点数量和边的数量：");\n scanf("%d %d", &vCount, &eCount);\n \n initGraph(&graph, vCount, eCount);\n \n printf("请输入边的起点、终点和权重（用空格隔开）：\n");\n for (int i = 0; i < eCount; i++) {\n int start, end, weight;\n scanf("%d %d %d", &start, &end, &weight);\n addEdge(&graph, start, end, weight);\n }\n \n printf("请输入源点：");\n scanf("%d", &start);\n \n dijkstra(&graph, start);\n \n return 0;\n}