Finding all the shortest paths between two nodes in unweighted directed graphs using BFS algorithm
- by andra-isan
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
