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

以下是一个使用迪杰斯特拉算法求解给定带权有向图G和源点v0到其余各点的最短路径的C语言代码：\n\nc\n#include <stdio.h>\n#include <stdbool.h>\n#define MAX_SIZE 100\n#define INF 99999\n\nvoid dijkstra(int G[MAX_SIZE][MAX_SIZE], int n, int src) {\n int dist[MAX_SIZE];\n bool visited[MAX_SIZE];\n \n // 初始化距离数组和访问数组\n for (int i = 0; i < n; i++) {\n dist[i] = INF;\n visited[i] = false;\n }\n \n // 源点到自身的距离为0\n dist[src] = 0;\n \n // 循环n次，每次找到距离源点最近的节点\n for (int count = 0; count < n - 1; count++) {\n int minDist = INF;\n int minDistNode;\n \n // 找到距离源点最近的未访问节点\n for (int i = 0; i < n; i++) {\n if (!visited[i] && dist[i] < minDist) {\n minDist = dist[i];\n minDistNode = i;\n }\n }\n \n // 将该节点标记为已访问\n visited[minDistNode] = true;\n \n // 更新与该节点相邻节点的距离\n for (int i = 0; i < n; i++) {\n if (!visited[i] && G[minDistNode][i] && dist[minDistNode] + G[minDistNode][i] < dist[i]) {\n dist[i] = dist[minDistNode] + G[minDistNode][i];\n }\n }\n }\n \n // 打印最短路径\n printf("最短路径为：\n");\n for (int i = 0; i < n; i++) {\n printf("从源点%d到节点%d的最短路径为：%d\n", src, i, dist[i]);\n }\n}\n\nint main() {\n int n; // 节点数\n int G[MAX_SIZE][MAX_SIZE]; // 带权有向图\n \n printf("请输入节点数：");\n scanf("%d", &n);\n \n printf("请输入带权有向图的邻接矩阵：\n");\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n scanf("%d", &G[i][j]);\n }\n }\n \n int src; // 源点\n printf("请输入源点：");\n scanf("%d", &src);\n \n dijkstra(G, n, src);\n \n return 0;\n}\n\n\n使用此代码，您可以输入节点数、带权有向图的邻接矩阵以及源点，然后程序将输出从源点到各个节点的最短路径。