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;

// there is a direct path between these two words, simply print that path as the shortest path
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));

//backtracing to  print all the nodes if gn is the same as our target node such as w.id
    if (gn == 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;
        //map1 keeps track of the visited nodes
        it = map1.find(p->first);
        graphNode gn1= p->second;
        if (it== map1.end())    {
            map<int, int>::iterator it1;

            //if the node already exits in the inQ, we do not insert it twice
            it1 = inQ.find(p->first);
            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