#include <queue>
#include <algorithm>
#include <string>
#include <list>

/**
 * Returns an std::list of vertex keys that creates any shortest path between `start` and `end`.
 *
 * This list MUST include the key of the `start` vertex as the first vertex in the list, the key of
 * the `end` vertex as the last element in the list, and an ordered list of all vertices that must
 * be traveled along the shortest path.
 *
 * For example, the path a -> c -> e returns a list with three elements: "a", "c", "e".
 *
 * You should use undirected edges. Hint: There are no edge weights in the Graph.
 *
 * @param start The key for the starting vertex.
 * @param end   The key for the ending vertex.
 */
template <class V, class E>
std::list<std::string> Graph<V,E>::shortestPath(const std::string start, const std::string end) {
  // TODO: Part 3

  std::list<std::string> path;
  std::unordered_map<string, bool> visited;
  std::queue<string> search_iter;
  std::unordered_map<string, string> predecessor;
  string temp;
  for(auto it = vertexMap.begin(); it != vertexMap.end(); it++){
    predecessor[it->first] = "empty_";
  }
  search_iter.push(start);
  predecessor[start] = "start";

  while(search_iter.empty() == false){
    temp = search_iter.front();
    search_iter.pop();
    for(auto it = vertexMap.begin(); it != vertexMap.end(); it++){
      bool hasneighbor = false;
      for(edgeListIter edgeit : adjList.at(temp)){
        if((*edgeit).get().source().key() == it->first || (*edgeit).get().dest().key() == it->first){
          hasneighbor = true;
        }
      }

      if(hasneighbor && predecessor[it->first] == "empty_"){
        predecessor[it->first] = temp;
        search_iter.push(it->first);

      }
    }
  }

  temp = end;
  path.push_back(end);
  while(temp != start){
    path.push_back(predecessor[temp]);
    temp = predecessor[temp];
  }
  std::reverse(path.begin(),path.end());

  return path;
}