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

/**
 * Returns an std::list of vertex keys that creates some 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".
 *
 * @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) {
  std::list<std::string> path;
  path.push_back(start);

  std::queue<Vertex> q;
  Vertex v = vertexMap[start];
  v["label"] = "visited";
  q.push(v);

  while (!q.empty()){
    v = q.front();
    q.pop();

    std::list<E_byRef> & incident = incidentEdges(v);

    for(E_byRef & edge :incident){
      Vertex adjacent = edge.get().dest();
      if (adjList["label"] != "visited"){
        edge["label"] = "discovered";
        adjacent["label"] = "visited";
      }
    }

  }





  return path;
}