Name: Anonymous 2009-01-26 14:02
LocationList& Graph::bfSearchForShortestPath(const Location &s, const Location &d, LocationList &route){
deque<Node> t;
Node v;
Node v_next;
int i;
nodes[s].visited=true;
nodes[s].pred=Location(0,0);
t.push_back(nodes[s]);
while(!t.empty() && nodes[t[0].loc].loc!=nodes[d].loc){
v=t[0];
v_next=nodes[v.adjList[0]];
i=1;
while(i<v.adjList.size() && v_next.visited){
v_next=nodes[v.adjList[i]]; i++;
}
if (!v_next.visited){
nodes[v_next.loc].visited=true;
nodes[v_next.loc].pred=v.loc;
t.push_back(v_next);
} else {
t.pop_front();
}
}
if (t.empty()) throw UnexpectedStateException("No Route");
route.clear();
v=nodes[d];
while(v.loc!=s){
route.push_front(v.loc);
v=nodes[v.pred];
}
route.push_front(s);
return route;
}Because I know everybody here loves C++ so much, have some random code.