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

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 开发者_如何学Cit1;
                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

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.

To write all of the shortest paths, you would have to write a recursive DFS-like algorithm. Run a BFS to find the minimum distance to each node, store that, and then run a DFS from the source node, only branching to nodes which satisfy the minimum path. Whenever you reach the target node, write the path you took to get there (which you have been keeping track of in your recursive function). Note that you will not be marking nodes in your DFS.

Since the algorithm requires backtracking, the best way to do it is via recursive DFS. You could write it with a BFS, but you would have to maintain a stack to keep track of your backtracking, which means you are essentially writing DFS with a manually maintained stack, i.e. writing the exact same algorithm with twice as much code as you need to.

Please be aware that the number of shortest paths is not always polynomial so you might be writing an exponential number of paths.