TimeShortPath(graph, s, way, D); for (int i = 0; i < 199; ++i) { if (way[e][i] == n) { c[n - 1] = i; std::cout << cities[i].city << ' '; n++; i = -1; } }

这段代码是一个寻找最短路径的算法中的一部分，其中 graph 是一个图的数据结构，s 表示起始节点，way 是一个二维数组，表示每个节点的前驱节点，D 是一个一维数组，表示起点到每个节点的最短路径长度。具体来讲，这段代码的作用是从终点反向寻找最短路径上的各个节点，并将它们依次存储在 c 数组中，输出路径上各个节点的名称。具体的实现流程如下：

1. 从终点 e 开始，通过 way 数组反向查找前驱节点，找到一个前驱节点 i，使得该节点到终点的路径长度最短。

2. 将该节点的索引 i 存储到 c 数组中，并输出该节点的名称。

3. 将节点数量 n 加1，表示已经找到了 n 个节点。

4. 将 i 赋值给循环变量 i，以便重新开始从该节点继续反向查找前驱节点。

5. 重复上述步骤，直到找到起点 s 为止。最终 c 数组中存储的就是从终点到起点的最短路径上的各个节点索引，以及输出路径上各个节点的名称。

相关问题

system("cls"); std::cout << "读取完成" << endl; std::cout << "请选择最短路径要求" << endl; std::cout << "时间：1 " << endl; std::cout << "价格：2 " << endl; cin >> p; system("cls"); switch (p) { case 1: std::cout << "以时间为基准：" << endl; TimeShortPath(graph, s, way, D); for (int i = 0; i < 199; ++i) { if (way[e][i] == n) { c[n - 1] = i; std::cout << cities[i].city << ' '; n++; i = -1; } } std::cout << std::endl; std::cout << "时间：" << D[e] << " h "; TxtWriting(graph, c, n); case 2: std::cout << "以价格为基准：" << endl; CostShortPath(graph, s, way, D); for (int i = 0; i < 199; ++i) { if (way[e][i] == n) { c[n - 1] = i; std::cout << cities[i].city << ' '; n++; i = -1; } } std::cout << std::endl; std::cout << "价格：$" << D[e]; TxtWriting(graph, c, n); }

这段代码实现了一个简单的控制台界面，让用户输入最短路径的要求（时间或价格），并调用相应的函数求解最短路径，并输出路径信息和路径花费。具体来说，该代码先清空控制台屏幕，然后输出提示信息，让用户选择最短路径要求。根据用户的选择，使用switch语句调用TimeShortPath或CostShortPath函数求解最短路径，并将路径保存在数组c中。然后遍历数组c，输出路径信息，并调用TxtWriting函数将路径信息输出到文本文件中。最后，根据用户选择的最短路径要求输出路径的时间或价格。

void shortest(const Graph& g, int depart, Way way[][199] ){ for (int i = 0; i < 199; i++) { for (int j = 0; j < 199; j++) { way[i][j].front = -1;//初始化赋值 } } for (int v = 0; v < g.vexnum; ++v) { g.vertex[v].pass = false;//初始化 way[depart][v].time= g.arcs[depart][v].time;//权重的记录 if(way[depart][v].time!=1000000&&v!=depart){ way[depart][v].front = depart; //将与出发点相通路径的前驱全部记为出发点的序号 } } way[depart][depart].time = 0; g.vertex[depart].pass = true;//出发点设置为true for (int i = 0; i < g.vexnum; ++i) { int v = 0; float mintime = 1000000; for (int w = 0; w < g.vexnum; ++w) { if (g.vertex[w].pass == false && way[depart][w].time < mintime) { v = w; mintime = way[depart][w].time; } }//用v记录最小权重边对应的点，并用mintime来储存最小权重的值 g.vertex[v].pass = true;//选出的点置为true,表示已选中 for (int w = 0; w < g.vexnum; w++) { if (g.vertex[w].pass == false && (mintime + g.arcs[v][w].time < way[depart][w].time)) {//将目前最短路径进行更新 way[depart][w].time = mintime + g.arcs[v][w].time; way[depart][w].front = v; } } } }代码存在错误，请用递归来将代码改写

好的，我会将代码改写为使用递归的形式：

void shortest(const Graph& g, int depart, Way way[][199], int v, int w) {
    if (v == g.vexnum) {
        return;
    }
    if (w == g.vexnum) {
        shortest(g, depart, way, v + 1, 0);
        return;
    }
    way[v][w].front = -1;
    if (v == depart) {
        way[v][w].time = g.arcs[depart][w].time;
        if (way[v][w].time != 1000000 && w != depart) {
            way[v][w].front = depart;
        }
    }
    else {
        way[v][w].time = way[v][w - 1].time;
        if (way[v][w].time > way[v - 1][w].time + g.arcs[v - 1][w - 1].time) {
            way[v][w].time = way[v - 1][w].time + g.arcs[v - 1][w - 1].time;
            way[v][w].front = v - 1;
        }
    }
    shortest(g, depart, way, v, w + 1);
}

这个递归函数的实现方式与原来的迭代方式有所不同。我们使用两个参数 v 和 w 来代替原来的两个循环变量 i 和 j。在每次递归调用中，我们先判断 v 和 w 是否已经达到了数组的边界，如果已经达到了边界就直接返回。

然后我们根据当前的 v 和 w 的值来初始化 way[v][w] 的值。如果 v 等于出发点 depart，那么我们直接将 way[v][w] 的时间赋值为从 depart 到 w 的时间，同时更新前驱结点。

如果 v 不等于 depart，那么我们将 way[v][w] 的时间先赋值为 way[v][w-1] 的时间。然后我们判断从 v-1 到 w 的时间加上 way[v-1][w] 的时间是否比当前的 way[v][w] 时间更小，如果更小的话就更新 way[v][w] 的时间，并将前驱结点设置为 v-1。

最后，我们递归调用 shortest 函数，将 w 的值加一。

这个函数的时间复杂度和迭代方式的时间复杂度是一样的，都是 O(n^2)。但是这个递归函数的代码更加简洁，易于理解。