Practice-It

Write a method named affordableFlights that accepts three parameters: (1) a Graph<String, String> parameter representing airline flights (like in the picture on the syntax reference sheet, where each vertex represents a city airport, each edge represents a flight, and the weight of each edge represents the cost of the flight in dollars); (2) a string representing a starting city; and (3) and an integer representing a maximum amount of money to spend. Your method should return an alphabetized Set of all cities that can be visited from that starting city on a path with a total cost of the given max amount or less (not including the starting city itself). For example, if a variable named graph represents the graph given by the picture below, the call of affordableFlights(graph, "PVD", 220) should return [DFW, LAX, LGA, ORD, SFO]. (You can just check vertex in the graph to see if it can be reached for the given cost limit, though this is not an ideal algorithm in terms of runtime.)

You are allowed to call methods on the graph but you should not modify its state. The graph passed to your method implements the following interface:

public interface Graph<V, E> {
    public void addEdge(V v1, V v2);
    public void addEdge(V v1, V v2, E e);
    public void addEdge(V v1, V v2, int weight);
    public void addEdge(V v1, V v2, E e, int weight);
    public void addVertex(V v);
    public void clear();
    public void clearEdges();
    public boolean containsEdge(E e);
    public boolean containsEdge(V v1, V v2);
    public boolean containsPath(List<V> path);
    public boolean containsVertex(V v);
    public int cost(List<V> path);
    public int degree(V v);
    public E edge(V v1, V v2);
    public int edgeCount();
    public Collection<E> edges();
    public int edgeWeight(V v1, V v2);
    public int inDegree(V v);
    public Set<V> inverseNeighbors(V v);
    public boolean isDirected();
    public boolean isEmpty();
    public boolean isReachable(V v1, V v2);         // depth-first search
    public boolean isWeighted();
    public List<V> minimumWeightPath(V v1, V v2);   // Dijkstra's algorithm
    public Set<V> neighbors(V v);
    public int outDegree(V v);
    public void removeEdge(E e);
    public void removeEdge(V v1, V v2);
    public void removeVertex(V v);
    public List<V> shortestPath(V v1, V v2);        // breadth-first search
    public String toString();
    public int vertexCount();
    public Set<V> vertices();
}