Dijkstra的算法的问题回溯顶点顶点、算法、问题、Dijkstra
我想实现回溯的顶点走访了最低成本路由到一个顶点。我得到不正确的结果，不明白为什么。唯一正确的输出是最后一个的形象。是什么原因造成的不正确
I'm trying to implement backtracing of the vertices visited for the lowest costing route to a vertex. I'm getting incorrect results and don't understand why. The only correct output was the last one in the image. What is causing the incorrect
注：driverMap是一个二维的14×14整数向量持有的距离才能到达每个顶点和路径是一个int数组来保存所采取的过去路径顶点。一开始是一款从我的主要功能code助阵。
Note: driverMap is a 2D 14x14 integer vector that holds the distances it takes to get to each vertex and path is a int array to hold the past path vertex taken. The beginning is a section of the code from my Main function to help out.
这是不同，因为我的previous问题是不同的，这一次我要求我的对预期的电流输出，帮助试图回溯的时候。
It's different as my previous questions were different, this time i'm asking for help on my current output against expected when attempting to backtrace.
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;
}
}
}
}
推荐答案
在djikstra做回溯
Doing backtracking in djikstra
记录，与较小的值更新当前节点的值的节点
Record the node that update the value of the current node with a smaller value
// 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
在您完成所有djikstra循环。从不同的起点任何一点原路返回。 再说了，我们想从5篇追踪到PT 0在你的图，其中5篇的起点。我们从0开始，拿回来[0]（应该等于4），那么我们就回去[4]（应该等于8），那么我们就回去[8]（应该等于5），那么，我们应该有一些种机制，停在这里的第5部分是一个起点。这样一来，你会得到0-4-8-5，你颠倒顺序。你得到的路径5-8-4-0。
After you have complete all djikstra looping. Backtrack from any point except the start point. Say, we want to trace from pt 5 to pt 0 in your graph where pt 5 is starting point. We start at 0, take back[0] (should equal to 4), then we take back[4] (should equal to 8), then we take back[8] (should equal to 5), then we should have some kinds of mechanism to stop here as pt 5 is a starting point. As a result, you get 0-4-8-5 and you reverse the order. You get the path 5-8-4-0.
在我的方法， pathTaken [minNode] .push_back（我）; 未使用。您可能需要启动int数组后面[]与那些谁被连接到起点出发点的价值。
In my approach, pathTaken[minNode].push_back(i); is not using. You might need to initiate the int array back[] with starting point's value for those who is connected to starting point.
修改部分
您错过了这一点：你可能需要启动int数组后面[]与那些谁被连接到起点出发点的价值
You miss the point: "You might need to initiate the int array back[] with starting point's value for those who is connected to starting point".
路径[K] = 0; 是错误的。你不应该主动与固定的指标适用于所有情况的路径。 相反，你应该startInt启动（对于那些直接连接到起始节点）和非存在的节点指数-1（对于那些没有直接连接到起始节点）
path[k] = 0; is wrong. You should not initiate path with fixed index for all cases. Instead, you should initiate with startInt (for those directly connected to starting node) and non-exist node index -1 (for those not directly connected to starting node)
什么回溯做的是
要记录哪些节点提供了一个新的最低成本为当前节点（和不断更新的Dijkstra算法循环）。最后，每个节点将获得一个节点值（返回[I] 在我的情况），其指向一个节点提供节点i与它的成本降至最低。
相应于Dijkstra算法与后台跟踪的概念，背[i]为在路径中从起点节点到节点i的previous节点。这意味着该路径应该是这样的：
to record which node provides a new minimum Cost to current node (and keep updating in dijkstra loop). At the end, every node will get a node value (back[i] in my case) that point to a node that provides node i with its minimize Cost.
Base on the concept of dijkstra algorithm with back-tracking, back[i] is the previous node in the path from starting node to node i. That mean the path should be looks like :
(start node)->(path with zero or more nodes)->node point by back[i]-> node i
应用这个概念，我们可以跟踪向后回[我]路径，背[返回[我]，背[背[背[I]]] ...
Applying this concept, we can track the path backward with back[i], back[back[i]], back[back[back[i]]],...
任何理由路径[K] = 0; 是错的？在您的code，你的出发点并不总是节点 0 ，但startint。考虑案件如 startint = 13 和目标目的节点 11 。很显然，路径是 13-11 。对于节点 11 ，它永远不会遇到距离[I] = minValue（最小值）+ driverMap [minNode] [我]; 时， startint = 13 在你的代码，因为这是第一个最小代价节点。而且你有什么设置？节点 11 的返回[11] = 0 （初始化），其中指出，在路径中的previous节点节点 13 到 11 的节点 0 这显然是不正确在概念上和背部[0] = 0（最好从13到0的路径是 13-0 ，没有更新也），这将循环自称为 0 =背[背[0] =背[背[背[0] = ... 。
Any why path[k] = 0; is wrong? In your code, your starting node is not always node 0, but startint. Consider case like startint = 13 and your target destination node is 11. Obviously, the path is 13-11. For node 11, it will never encounter Distances[i] = minValue + driverMap[minNode][i]; when startint = 13 in your coding because that is first minimum cost node. And what have you set? node 11 has back[11]=0 (initialization) which state that the previous node in the path node 13 to 11 is node 0 which is obviously incorrect in concept and back[0]=0 (best path from 13 to 0 is 13-0, no update also) which will loop to itself as 0=back[back[0]]=back[back[back[0]]]=....
