SHARE
TWEET

Untitled

a guest Dec 10th, 2019 96 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <queue>
  2. #include <algorithm>
  3. #include <string>
  4. #include <list>
  5.  
  6. /**
  7.  * Returns an std::list of vertex keys that creates any shortest path between `start` and `end`.
  8.  *
  9.  * This list MUST include the key of the `start` vertex as the first vertex in the list, the key of
  10.  * the `end` vertex as the last element in the list, and an ordered list of all vertices that must
  11.  * be traveled along the shortest path.
  12.  *
  13.  * For example, the path a -> c -> e returns a list with three elements: "a", "c", "e".
  14.  *
  15.  * You should use undirected edges. Hint: There are no edge weights in the Graph.
  16.  *
  17.  * @param start The key for the starting vertex.
  18.  * @param end   The key for the ending vertex.
  19.  */
  20. template <class V, class E>
  21. std::list<std::string> Graph<V,E>::shortestPath(const std::string start, const std::string end) {
  22.   // TODO: Part 3
  23.  
  24.   std::list<std::string> path;
  25.   std::unordered_map<string, bool> visited;
  26.   std::queue<string> search_iter;
  27.   std::unordered_map<string, string> predecessor;
  28.   string temp;
  29.   for(auto it = vertexMap.begin(); it != vertexMap.end(); it++){
  30.     predecessor[it->first] = "empty_";
  31.   }
  32.   search_iter.push(start);
  33.   predecessor[start] = "start";
  34.  
  35.   while(search_iter.empty() == false){
  36.     temp = search_iter.front();
  37.     search_iter.pop();
  38.     for(auto it = vertexMap.begin(); it != vertexMap.end(); it++){
  39.       bool hasneighbor = false;
  40.       for(edgeListIter edgeit : adjList.at(temp)){
  41.         if((*edgeit).get().source().key() == it->first || (*edgeit).get().dest().key() == it->first){
  42.           hasneighbor = true;
  43.         }
  44.       }
  45.  
  46.       if(hasneighbor && predecessor[it->first] == "empty_"){
  47.         predecessor[it->first] = temp;
  48.         search_iter.push(it->first);
  49.  
  50.       }
  51.     }
  52.   }
  53.  
  54.   temp = end;
  55.   path.push_back(end);
  56.   while(temp != start){
  57.     path.push_back(predecessor[temp]);
  58.     temp = predecessor[temp];
  59.   }
  60.   std::reverse(path.begin(),path.end());
  61.  
  62.   return path;
  63. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top