Мне нужна помощь, чтобы узнать, как правильно сохранить направления из путаницы в алгоритме Джикстра

Question

Я использую версию алгоритма Джикстра, которую я изменил, чтобы использовать кортеж, потому что мне нужно вернуть три вещи с этой функцией.Направления, рассчитанное расстояние и время выполнения для линии, следующей за автомобильным проектом.

В настоящее время я представляю направления в виде чисел.Пример: 1- Вперед.

Вся проблема в том, что время выполнения и рассчитанная дистанция отлично работают.

Я пробовал множество способов получить правильный набор «направлений».внутри вектора.Но по завершении программы вектор хранит больше направлений, чем следует, в том числе и из других путей.

Какое правило я могу составить, чтобы оно сохраняло только направления от пути, который он вычисляет, непосредственно от источника к месту назначения?

tuple <vector<int>, int, double> Djikstra::dijkstra(int orig, int dest)
{
    time_t start, end;
    time(&start);
    ios_base::sync_with_stdio(false);

    vector<int> directions;
    int dist[V];
    int visitted[V];

    priority_queue < tuple<int, int, int>,
            vector<tuple<int, int, int> >, greater<tuple<int, int, int> > > pq;

    for(int i = 0; i < V; i++)
    {
        dist[i] = INFINITE;
        visitted[i] = false;
    }

    dist[orig] = 0;

    pq.push(make_tuple(dist[orig], orig, orig));

    while(!pq.empty())
    {
        tuple<int, int, int> p = pq.top();
        int u = get<1>(p);
        pq.pop(); // remove da fila

        if(visitted[u] == false)
        {
            visitted[u] = true;

            list<tuple<int, int, int> >::iterator it;

            for(it = adj[u].begin(); it != adj[u].end(); it++)
            {
                int v = get<0>(*it);
                int edge_cost = get<1>(*it);
                int direction = get<2>(*it);

                if(dist[v] > (dist[u] + edge_cost))
                {
                    //directions.push_back(direction); //This is the line I used 
                    dist[v] = dist[u] + edge_cost;
                    pq.push(make_tuple(dist[v], v, v));
                }

            }

        }
    }
    time(&end);
    double time_taken = double(end - start);
    return make_tuple(directions, dist[dest], time_taken);
}

Во время теста с предварительно установленным списком смежности,Вывод вычисленного вектора направлений должен составлять 2 направления, вместо этого я получил 5 позиций.