void CostShortPath(Graph G, int v0, int**& P, float*& D) { // P 的int类型二维数组是为了按顺序输出更方便 所以 P 的某一个值应该代表 顺序 int v, w; P = new int* [199]; bool final[199]; // final 是一个长度为 199 的 bool 类型一维数组 // final[v] 为 true 当且仅当 v 已经实现最短路径 for (int p = 0; p < 199; ++p) { P[p] = new int[199]; } D = new float[199]; for (v = 0; v < 199; ++v) { final[v] = false; D[v] = G.arcs[v0][v].cost; for (int w = 0; w < 199; ++w) P[v][w] = 0; if (D[v] < INFINITY) {// v代表的是 和起点直接相连的城市索引 P[v][v0] = 1; P[v][v] = 2; } } D[v0] = 0; final[v0] = true; for (int i = 1; i < 199; ++i) { // 其他198个顶点 float min = INFINITY; for (w = 0; w < 199; ++w) { // 寻找“次短路径” if (!final[w]) { if (D[w] < min) { v = w; min = D[w]; } } } final[v] = true; for (w = 0; w < 199; ++w) { if (!final[w] && (min + G.arcs[v][w].cost < D[w])) { D[w] = min + G.arcs[v][w].cost; memcpy(P[w], P[v], 199 * sizeof(int)); P[w][w] = P[v][v] + 1; } } } }

这段代码是关于最短路径算法的实现，采用的是Dijkstra算法。该函数接收三个参数：图G、起点v0和两个输出参数P和D，其中P是int类型的二维数组，D是float类型的一维数组。首先，定义一个bool类型的数组final来标记每个顶点是否已经实现最短路径，其中所有元素初始值为false。然后定义一个二维数组P和一维数组D，分别用来记录顶点的最短路径和最短路径的长度。接下来，对于每个顶点v，将D[v]初始化为起点v0到v的距离，将P[v]初始化为空路径，并将与起点v0直接相连的顶点的P[v]和P[v0]赋初值1和2。然后将起点v0的D[v0]赋初值为0，final[v0]赋初值为true。接下来进入for循环，重复执行199次，每次选出一个未实现最短路径的顶点v，使得D[v]值最小，将其标记为已实现最短路径，并更新其邻接顶点的最短路径和最短距离。通过循环实现了对整个图的最短路径计算。最终输出的P和D数组记录了起点v0到每个顶点的最短路径和最短距离。