问题描述 给定无向图带权图的数据类型如下 #define MAXVEX 100 typedef char VertexType; typedef int EdgeType; typedef struct { VertexType vexs[MAXVEX]; //顶点表 EdgeType edge[MAXVEX][MAXVEX]; //邻接矩阵,即边表 int vertexNum,edgeNum; } MGraph,*Graph; 请设计void Dijkstra(Graph g, int s, int D[], int P[])函数。 该函数计算编号为s的顶点点到所有顶点的最短路径长度及最短路径。 如果顶点不可达，则最短路径为INT_MAX。 数组D[]记录顶点s到对应顶点的最短距离(s到s的最短路径长度为0) 数组P[]记录顶点s到对应顶点的最短路径上的前驱(终点的前驱，特别的i到i的前驱为i)。 请注意，本题有预置代码，只需提交所要求的函数定义代码即可。 预置代码 include<bits/stdc++.h> using namespace std; #define MAXVEX 100 typedef char VertexType; typedef int EdgeType; typedef struct { VertexType vexs[MAXVEX]; //顶点表 EdgeType edge[MAXVEX][MAXVEX]; //邻接矩阵,即边表 int vertexNum,edgeNum; } MGraph,*Graph; void Dijkstra(Graph g, int s, int D[], int P[]); int main() { /*此处代码由测试程序自动添加，主要为了向顺序表中插入数据 并输出数据,你无需关心此处代码的具体实现细节。 如果有必要，请自己添加代码以测试你的函数是否正确。 */ return 0; } /*你的提交的代码将被添加在此处，请完成题目所要求的函数的定义*/c语言代码

void Dijkstra(Graph g, int s, int D[], int P[]) {
int i, j, k;
int min;
int visited[MAXVEX]; // 标记数组，标记顶点是否被访问过

// 初始化
for (i = 0; i < g->vertexNum; i++) {
visited[i] = 0; // 标记数组初始化为未访问
D[i] = g->edge[s][i]; // 最短距离初始化为s到i的距离
P[i] = (D[i] == INT_MAX) ? -1 : s; // 前驱结点初始化为s或-1
}
visited[s] = 1; // 标记起始结点已访问
D[s] = 0; // 起始结点到自身的距离为0

// Dijkstra算法核心部分，遍历所有结点
for (i = 1; i < g->vertexNum; i++) {
// 找到未访问结点中距离起始结点最近的结点
min = INT_MAX;
for (j = 0; j < g->vertexNum; j++) {
if (!visited[j] && D[j] < min) {
min = D[j];
k = j;
}
}
visited[k] = 1; // 标记该结点已访问

// 更新未访问结点的最短距离和前驱结点
for (j = 0; j < g->vertexNum; j++) {
if (!visited[j] && (D[k] + g->edge[k][j] < D[j])) {
D[j] = D[k] + g->edge[k][j];
P[j] = k;
}
}
}
}