c++ - 带回溯顶点的 Dijkstra 算法问题

Question

我正在尝试实现对访问的顶点的回溯，以获得到达顶点的最低成本路径。我得到不正确的结果，不明白为什么。唯一正确的输出是图像中的最后一个。是什么导致不正确

注意:driverMap 是一个 2D 14x14 整数 vector ，它保存到达每个顶点所需的距离，而 path 是一个 int 数组，用于保存过去的路径顶点。开头是我的 Main 函数中的一段代码以提供帮助。

这是不同的，因为我之前的问题不同，这次我在尝试回溯时寻求有关我当前输出与预期输出的帮助。

for(int i = 0; i < allCars.size(); i++) //allCars.size()

{

    int startInt = allCars[i].getStart(), loopEnder = 0;



    for(int k = 0; k < driverMap.size(); k++)
    {
        path[k] = 0;
        Distances[k] = 0;
    }


    for(int j = 0; j < driverMap.size(); j++) 

    {

        Distances[j] = driverMap[startInt][j];

    }

    cout << "\nSTART INTERSECTION: '" << startInt << "' END INTERSECTION: '" << allCars[i].getEnd() << "'" <<  endl;


    Dijkstra(driverMap, Distances, path, startInt);

    int endInt = allCars[i].getEnd(), atInt = path[endInt];

    cout << "END = " << endInt;

    //allCars[i].addPath(endInt);
    do
    {
        cout << "AT = " << atInt;
        allCars[i].addPath(atInt);
        atInt = path[atInt];
        loopEnder++;
    }while(atInt != endInt && loopEnder < 5);
    cout << endl;

    //allCars[i].addPath(startInt);


    allCars[i].displayCar();

}

void Dijkstra(const vector< vector<int> > & driverMap, int Distances[], int path[], int startInt) 
{
    int Intersections[driverMap.size()];
    for(int a = 0; a < driverMap.size(); a++)
    {
        Intersections[a] = a;
    }
    Intersections[startInt] = -1;

    for(int l = 0; l < driverMap.size(); l++)
    {
        int minValue = 99999;

        int minNode = 0;




        for (int i = 0; i < driverMap.size(); i++) 

        {

            if(Intersections[i] == -1) 

            {

                continue;

            }

            if(Distances[i] > 0 && Distances[i] < minValue)

            {

                minValue = Distances[i];

                minNode = i;

            }

        }


        Intersections[minNode] = -1;





        for(int i = 0; i < driverMap.size(); i++) 

        {

            if(driverMap[minNode][i] < 0)

            {

                continue;

            }

            if(Distances[i] < 0) 

            {

                Distances[i] = minValue + driverMap[minNode][i];
                path[i] = minNode;

                continue;

            }

            if((Distances[minNode] + driverMap[minNode][i]) < Distances[i]) 

            {

                Distances[i] = minValue + driverMap[minNode][i];
                path[i] = minNode;

            }

        }
    }

}

Answer 1

在 djikstra 中做回溯

1. 用较小的值记录更新当前节点值的节点

   // Every time you update distance value with a smaller value
   Distances[i] = minValue + driverMap[minNode][i];
   back[i] = minNode;  //Record the node with an int array, should be something like this
   

2. 在您完成所有 djikstra 循环之后。从起点以外的任意点回溯。比如说，我们想在你的图表中从 pt 5 追踪到 pt 0，其中 pt 5 是起点。我们从0开始，取回[0](应该等于4)，然后我们取回[4](应该等于8)，然后我们取回[8](应该等于5)，那么我们应该有一些各种机制到此为止，因为第 5 部分是起点。结果，您得到 0-4-8-5 并且您颠倒了顺序。你得到路径 5-8-4-0。

在我的方法中，pathTaken[minNode].push_back(i); 没有使用。对于那些连接到起点的人，您可能需要使用起点的值来启动 int 数组 back[]。

---

编辑部分

您错过了要点:“对于连接到起点的人，您可能需要使用起点的值来启动 int 数组 back[]”。

path[k] = 0; 是错误的。您不应在所有情况下都使用固定索引启动路径。 相反，您应该使用 startInt(对于那些直接连接到起始节点的节点)和不存在的节点索引 -1(对于那些没有直接连接到起始节点的节点)

回溯做的是

1. 记录哪个节点为当前节点提供了新的最小成本(并在 dijkstra 循环中不断更新)。最后，每个节点都将获得一个节点值(在我的例子中为 back[i])，该值指向为节点 i 提供最小成本的节点。

2. 基于带回溯的dijkstra算法的概念，back[i]是从起始节点到节点i的路径中的前一个节点。这意味着路径应该是这样的:

   (start node)->(path with zero or more nodes)->node point by back[i]-> node i
   

应用这个概念，我们可以用 back[i], back[back[i]], back[back[back[i]]],...向后追踪路径

为什么 path[k] = 0; 是错误的？在您的代码中，您的起始节点并不总是节点 0，而是 startint。考虑像 startint = 13 这样的情况，您的目标节点是 11。显然，路径是13-11。对于节点 11，它永远不会遇到 Distances[i] = minValue + driverMap[minNode][i]; 当 startint = 13 在你的编码，因为这是第一个最小成本节点。你设置了什么？节点 11 有 back[11]=0(初始化)，表示路径节点 13 到 11< 中的前一个节点 是节点 0，这在概念上显然是不正确的，back[0]=0(从 13 到 0 的最佳路径是 13-0，也没有更新)将循环到自身作为 0=back[back[0]]=back[back[back[0]]]=...。