Как сохранить кратчайший путь из всех узлов данного узла в то время как BFS? - PullRequest
Новая
       6

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

0 голосов
/ 09 апреля 2020

Я делаю вопрос графика, и здесь я использую BFS. Я знаю, что BFS дает нам кратчайший путь от данного узла ко всем другим узлам в массиве, но я также хочу сохранить узлы, включенные в этот кратчайший путь. Как я могу добиться этого -

Вот часть моего кода - 

void bfsUtil(ll src, ll *pred, ll *dist, bool *visited){

        queue<ll> q;
        visited[src]=true;
        dist[src]=0;
        q.push(src);

        // an array of vector to store the path between a given node to all the other node.
        vector<ll> path[V+1];
        for(int i=0; i<=V; i++){
            // pushed back source first in every path as source node will definitely going to be there. 
            path[i].push_back(src);
        }

        while (!q.empty())
        {
            ll u = q.front();
            q.pop();

            for(ll i=0; i<adj[u].size(); i++){
                if(!visited[adj[u][i]]){
                    visited[adj[u][i]]=true;
                    dist[adj[u][i]]=dist[u]+1;
                    pred[adj[u][i]]=u;
                    q.push(adj[u][i]);

                    // pushing the node and its parent-
                    path[adj[u][i]].push_back(u);
                    path[adj[u][i]].push_back(adj[u][i]);
                }
            }
        }

        for(int i=0; i<=V; i++){
            for(int j=0; j<path[i].size(); j++) cout << path[i][j] << " ";
            cout << "\n";
        }

    }

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

...