//在所有未被访问的顶点中查找dist值最小的顶点，返回其索引值 //当所有顶点均被访问过，返回-1 int SearchMin(Graph G) { /*------------代码开始--------------*/ /*------------代码结束--------------*/ } //更新第v个顶点的所有未被访问的邻接点的索引与距起点的最小距离 void UpdatePath(Graph G, int v) {

/*------------代码开始--------------*/
int minDist = INT_MAX; //初始化最小距离为正无穷
int minIndex = -1; //初始化最小距离点的索引为-1
for (int i = 0; i < G.vertexNum; i++) { //遍历所有顶点
if (!G.visited[i] && G.dist[i] < minDist) { //如果当前顶点未被访问且距起点的距离比当前最小距离小
minDist = G.dist[i]; //更新最小距离
minIndex = i; //更新最小距离点的索引
}
}
G.visited[minIndex] = true; //将最小距离点标记为已访问
for (int i = 0; i < G.vertexNum; i++) { //遍历所有顶点
if (!G.visited[i] && G.matrix[minIndex][i] < INT_MAX) { //如果当前顶点未被访问且与最小距离点有边相连
int newDist = G.dist[minIndex] + G.matrix[minIndex][i]; //计算起点到该点的距离
if (newDist < G.dist[i]) { //如果新距离比之前的距离更小
G.dist[i] = newDist; //更新距起点的最小距离
G.path[i] = minIndex; //更新该点在最短路径上的前一个顶点
}
}
}
}
/*------------代码结束--------------*/