I want to get full path in adjacency list Dijkstra algorithm using C queue. Graph edges are oriented.

Dijkstra algorithm works fine and I understand why. However getting full path is a bit more complicated to me, this usually described much less than Dijkstra algorithm itself. I tried to reused a few solutions (this, for example) I've found for square matrix, but it didn't worked for my adjacency list implementation.

Part I'm stucked with:

int dijkstra(int start, int finish)
{
    //some code
    parent.resize(vertex_count(), -1);
    while (!q.empty()) {
        //some code
        for (auto edge : link[current]) {
            if (dist[current]   edge.weight < dist[edge.to]) {
                dist[edge.to] = dist[current]   edge.weight;
                parent[edge.to] = start;
                q.push(QueueVertex(edge.to,dist[edge.to]));
            }
        }
    }
    path(parent);
    return dist[finish];
}
void path(vector<int> parent) {
    for (auto i = 0; i < parent.size(); i  ) {
        if (parent[i] != -1)
            cout << i << ' ';
    }
    cout << endl;
}

Full code:

    #include <iostream>
    #include <queue>
    #include <algorithm>
    #include <vector>
    #include <climits>
    #define INF INT_MAX
    using namespace std;
    
    struct Edge
    {
        int to;
        int weight;
        Edge() {}
        Edge(int to, int weight) : to(to), weight(weight) {}
        void read() {
            cin >> to >> weight;
        }
    };
    struct QueueVertex
    {
        int number;
        int dist;
        QueueVertex(int number, int dist) : number(number), dist(dist) {}
    };
    bool operator<(const QueueVertex& v1, const QueueVertex& v2) {
        return v1.dist > v2.dist;
    }
    class Graph
    {
        vector<vector<Edge>> link;
        vector <int> dist;
        vector<int> parent = {};
    public:
        Graph(int vertex_count) :
            link(vertex_count) {}
        void add_edge_u(int from, int to, int weight) { //unoriented
            link[from].push_back(Edge(to, weight));
            link[to].push_back(Edge(from, weight));
        }
        void add_edge_o(int from, int to, int weight) { //oriented
            link[from].push_back(Edge(to, weight));
        }
        int vertex_count() const {
            return link.size();
        }
        int dijkstra(int start, int finish)
        {
            dist.resize(vertex_count(), INF);
            dist[start] = 0;
            parent.resize(vertex_count(), -1);
            priority_queue <QueueVertex> q;
            q.push(QueueVertex(start, 0));
            while (!q.empty()) {
                int current = q.top().number;
                int current_dist = q.top().dist;
                q.pop();
                if (current_dist > dist[current]) {
                    continue;
                }
                for (auto edge : link[current]) {
                    if (dist[current]   edge.weight < dist[edge.to]) {
                        dist[edge.to] = dist[current]   edge.weight;
                        parent[edge.to] = start;
                        q.push(QueueVertex(edge.to,dist[edge.to]));
                    }
                }
            }
            path(parent);
            return dist[finish];
        }
        void path(vector<int> parent) {
            for (auto i = 0; i < parent.size(); i  ) {
                if (parent[i] != -1)
                    cout << i << ' ';
            }
            cout << endl;
        }
    };
    
    
    int main()
    {
{
    int n = 3, m = 3, start = 1, finish = 0;
    Graph gr(n);
    gr.add_edge_o(0, 1, 1);
    gr.add_edge_o(1, 2, 2);
    gr.add_edge_o(2, 3, 5);
    gr.add_edge_o(3, 0, 4);
    int dist = gr.dijkstra(start, finish);
    cout << dist << endl;
        return 0;
    }

Desirable output (program getting 11 just fine, but not 1 2 3 0 part):

1 2 3 0
11

Thank you.

CodePudding user response：

Your path function makes no sense. You should be using the parent array to walk backwards from the goal state to the start. As written, this function simply outputs all the parents. Consider something like this:

deque<int> path;
while(finish != -1)
{
    path.push_front(finish);
    finish = (finish == start) ? -1 : parent[finish];
}

for (int node : path) cout << (node   1) << ' ';
cout << endl;

Note that the above uses a std::deque for convenience, since the path is built in reverse. But you can use a std::vector if you wish, and either reverse it or walk over it with a reverse_iterator.

Now that the path is being built correctly, you'll quickly see another problem, which is that your parent table is not being built correctly. You're doing this:

parent[edge.to] = start;    //<-- incorrect

That looks like a copy/paste error, because you don't want every node's parent to point back at the start. The parent of the edge being examined is stored in current:

parent[edge.to] = current;  //<-- correct