SHARE
TWEET

Untitled

a guest Dec 11th, 2019 88 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.     std::list<std::string> path;
  2.  
  3.     // no Dijkstra :(
  4.     // initialization
  5.     queue<string> q;
  6.     unordered_map<string, bool> labels; // {vertex, flag}
  7.     unordered_map<string, string> prev; // {vertex, previous vertex}
  8.     labels[start] = true;
  9.     q.push(start);
  10.     while(!q.empty()){
  11.         string v = q.front();
  12.         q.pop();
  13.         for(auto e : incidentEdges(v)){
  14.             string w = e.get().dest().key();
  15.             string source = e.get().source().key(); // something else is the source of adj
  16.             if(labels.find(w) == labels.end()){ // unexplored
  17.                 labels[w] = true; // set to explored (discovery)
  18.                 prev[w] = v; // keep track of previous
  19.                 q.push(w); // add to queue
  20.             }
  21.             if(isAdjacent(source, v) && labels.find(source) == labels.end()){ // undirected
  22.                 labels[source] = true; // set to explored (discovery)
  23.                 prev[source] = v; // keep track of previous
  24.                 q.push(source); // add to queue
  25.             }
  26.             if(labels.find(end) != labels.end()){ // reached end vertex
  27.                 path.push_front(end); // add to path in reverse order
  28.                 string p = prev.at(end);
  29.                 while(p != start){
  30.                     path.push_front(p);
  31.                     p = prev.at(p);
  32.                 }
  33.                 path.push_front(start);
  34.                 return path;
  35.             }
  36.  
  37.         }
  38.     }
  39.     return path;
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top