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;
时间: 2024-04-27 16:23:53 浏览: 74
A* Pathfinding Project
这段代码实现了Dijkstra算法的核心部分,用于求图G中从起点v0到其他所有顶点的最短路径。具体来说,该函数接受一个Graph类型的参数G,表示要求解的图;一个整数v0,表示起点的索引;一个指向int类型二维数组的指针P,用于记录最短路径上的顶点;一个指向float类型数组的指针D,用于记录最短路径的长度。
函数首先创建一个二维数组P,用于记录最短路径上的顶点。然后,对于图中的每一个顶点v,将final[v]设置为false,将D[v]初始化为从起点v0到v的边的权值,将P[v][w]初始化为0,表示路径上没有经过w这个顶点。如果D[v]小于无穷大(即从v0存在一条到v的边),则将P[v][v0]设置为1,将P[v][v]设置为2,表示路径上先经过v0,再经过v。
接下来,将起点v0的final[v0]设置为true,表示v0已经找到了最短路径。
阅读全文