Finding all the shortest paths between two nodes in unweighted directed graphs using BFS algorithm

Question

Hi All, I am working on a problem that I need to find all the shortest path between two nodes in a given directed unweighted graph. I have used BFS algorithm to do the job, but unfortunately I can only print one shortest path not all of them, for example if they are 4 paths having lenght 3, my algorithm only prints the first one but I would like it to print all the four shortest paths. I was wondering in the following code, how should I change it so that all the shortest paths between two nodes could be printed out?

class graphNode{
    public:
        int id;
        string name;
        bool status;
        double weight;
};


map<int, map<int,graphNode>* > graph; 


int Graph::BFS(graphNode &v, graphNode &w){

    queue <int> q;
    map <int, int> map1;  // this is to check if the node has been visited or not.
    std::string str= "";
    map<int,int> inQ;  // just to check that we do not insert the same iterm twice in the queue


    map <int, map<int, graphNode>* >::iterator pos;
    pos = graph.find(v.id);
    if(pos == graph.end()) {
        cout << v.id << " does not exists in the graph " <<endl;
        return 1;

    }

    int parents[graph.size()+1];   // this vector keeps track of the parents for the node
    parents[v.id] = -1;


    if (findDirectEdge(v.id,w.id) == 1 ){
        cout << " Shortest Path: " << v.id << " -> " << w.id << endl;
        return 1;
    } //if
    else{
        int gn;
        map <int, map<int, graphNode>* >::iterator pos;

        q.push(v.id);
        inQ.insert(make_pair(v.id, v.id));

        while (!q.empty()){
        gn = q.front();
        q.pop();
        map<int, int>::iterator it;
        cout << " Popping: " << gn <<endl;
        map1.insert(make_pair(gn,gn));


        if (gn == w.id){//backtracing to  print all the nodes if gn is the same as our target node such as w.id
            int current = w.id;
            cout << current << " - > ";
            while (current!=v.id){
                current = parents[current];
                cout << current << " -> ";
            }
        cout <<endl;
        }
                          if ((pos = graph.find(gn)) == graph.end()) {
            cout << " pos is empty " <<endl;
            continue;
        }
        map<int, graphNode>* pn = pos->second;

                          map<int, graphNode>::iterator p = pn->begin();
        while(p != pn->end()) {
            map<int, int>::iterator it;

            it = map1.find(p->first);//map1 keeps track of the visited nodes
            graphNode gn1= p->second;
            if (it== map1.end())    {
                map<int, int>::iterator it1;
                it1 = inQ.find(p->first);  //if the node already exits in the inQ, we do not insert it twice

                if (it1== inQ.end()){
                    parents[p->first] = gn;
                    cout << " inserting " << p->first << " into the queue " <<endl;
                    q.push(p->first);  // add it to the queue
                } //if
            }  //if
            p++;
          } //while

    } //while
}

I do appreciate all your great help Thanks, Andra

Answer 1

1. map<int, map<int,graphNode>* > graph declares a graph with one graphNode object per edge.

   One graphNode per node would have type map<int, map<int,graphNode*> > or, even better, map<graphNode*, set /* or vector */<graphNode*> >, or perhaps better yet, multimap< graphNode *, graphNode * >.

   The graphNodes need to be stored in a separate structure (say, vector or deque) from whatever map you use.

2. int parents[graph.size()+1]; is nonstandard. Use vector<int> parents( graph.size()+1 ); instead.

3. To answer your question, you want to continue the BFS until you reach the first node of topological order greater than the first result. Introduce a variable int first_id_of_next_level = v.id;. (Or better, use a pointer.) When you find a match, append its path to a list of paths. When gn == first_id_of_next_level, either return the list if it is not empty or set first_id_of_next_level = p->first, the first child of the current parent, so you know the next opportunity to stop the search.