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::queue<std::string> path_;
  std::unordered_map<std::string, std::string> currentToOrigin;
  std::unordered_map<std::string, bool> visited;

  for (std::pair<std::string, V_byRef> v : vertexMap) {
    visited.insert(std::pair<std::string, bool>(v.first, false));
    // std::cout << visited.at(v.first) << std::endl;
  }

  // std::cout << "start bfs" << std::endl;

  path_.push(start);

  while (!(path_.empty())) {
    string v_ = path_.front();
    // V & v = *(new V(v_));
    path_.pop();
    bool & flag = visited.at(v_);
    flag = true;

    // for (auto e : incidentEdges(v_)) {
    //   if (visited.at((e.get()).dest().key()) == false) {
    //     path_.push((e.get()).dest().key());
    //     currentToOrigin.insert(std::pair<std::string, std::string>((e.get()).dest().key(), v_));
    //   }
    // }
    for (std::pair<std::string, V_byRef> v : vertexMap) {
      if (isAdjacent(v_, v.first)) {
        if (visited.at(v.first) == false) {
          path_.push(v.first);
          currentToOrigin.insert(std::pair<std::string, std::string>(v.first, v_));
        }
      }
    }
  }

  // std::cout << currentToOrigin.size() << std::endl;
  // std::cout << "here" << std::endl;

  string currentV = end;
  while (currentV != start) {
    path.push_back(currentV);
    currentV = currentToOrigin.at(currentV);
  }

  path.push_back(start);
  path.reverse();

  return path;
}