Dijkstra’s Algorithm problems with backtracing vertexes

Question

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

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.

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;

            }

        }
    }

}

Answer 1

Doing backtracking in djikstra

1. 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
   

2. 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.

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.

---

Edit Part

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".

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)

What back-tracking doing is

1. 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.

2. 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
   

Applying this concept, we can track the path backward with back[i], back[back[i]], back[back[back[i]]],...

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]]]=....

Answer 2

In djikstra if you go backwards (finnish -> start) just pick lowest cost node at each step to reach staring point. This works after you have solved graph and you have each node evaluated/costed.