问题描述 给定无向图带权图的数据类型如下 #define MAXVEX 200 //最大顶点数 typedef char VertexType; typedef struct ENode { int adjVertex; //该边所指的顶点编号 int weight; //边权 struct ENode *nextEdge; //下一条边 } ENode; typedef struct VNode { VertexType data; //顶点信息 int visited; //遍历标记. 1:已遍历 0:未遍历 ENode *firstEdge; //第一条出边 } VNode; typedef struct { VNode vexs[MAXVEX]; int vertexNum,edgeNum; //点数和边数 }AdjGraph,*Graph; 请设计void Dijkstra(Graph g, int s, int D[], int P[])函数。 该函数计算编号为s的顶点到所有顶点的最短路径长度及最短路径。 如果顶点不可达，则最短路径为INT_MAX。 数组D[]记录顶点s到对应顶点的最短距离(s到s的最短路径长度为0) 数组P[]记录顶点s到对应顶点的最短路径上的前驱(s到s的前驱为s)。 请注意，本题有预置代码，只需提交所要求的函数定义代码即可。 预置代码 include<bits/stdc++.h> using namespace std; #define MAXVEX 200 //最大顶点数 typedef char VertexType; typedef struct ENode { int adjVertex; //该边所指的顶点编号 int weight; //边权 struct ENode *nextEdge; //下一条边 } ENode; typedef struct VNode { VertexType data; //顶点信息 int visited; //遍历标记. 1:已遍历 0:未遍历 ENode *firstEdge; //第一条出边 } VNode; typedef struct { VNode vexs[MAXVEX]; int vertexNum,edgeNum; //点数和边数 }AdjGraph,*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]; // 标记数组，标记顶点是否被访问过
ENode *p;

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

// 更新起始结点的邻接结点的最短距离和前驱结点
p = g->vexs[s].firstEdge;
while (p != NULL) {
D[p->adjVertex] = p->weight;
P[p->adjVertex] = s;
p = p->nextEdge;
}

// 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; // 标记该结点已访问

// 更新未访问结点的最短距离和前驱结点
p = g->vexs[k].firstEdge;
while (p != NULL) {
if (!visited[p->adjVertex] && (D[k] + p->weight < D[p->adjVertex])) {
D[p->adjVertex] = D[k] + p->weight;
P[p->adjVertex] = k;
}
p = p->nextEdge;
}
}
}