CS 1501代做、代写Python/Java程序设计

日期：2024-04-07 09:22

Support for Assignment 4

CS 1501

Sherif KhattabGeneral Hints

• You can get the number of vertices using ag.getAirports().size(), whereby

ag is an AirlineGraph object

• Iterate over airports using for(String airport: ag.getAirports()){ … }

• You can get a unique integer for each airport in the graph using the

ag.getAirportNo() method

• You can retrieve the set of neighbors of an airport using

ag.adj(airportName)

• To iterate over the set of neighbors: for(Route r: ag.adj(airportName)){ … }

• You can retrieve the name of a neighboring airport using r.destination

• You may use HashSet to instantiate Set objectsfewestStops

• Use BFS

• check the pseudo-code in lecture notes

• Shortest path Source -> transit -> destination can be found by

• shortest path source  transit

• shortest path transit  destination

• concatenate the two shortest paths

• Be careful not to add transit twice to the concatenated pathConnected Components

• Use BFS

• You can find the pseudo-code in the lecture notesallTrips

• Use backtracking and pruning

• Define a recursive helper method: solve(current decision, current solution)

• current decision  current vertex (int or String) • current solution

• Set<ArrayList<Route>> of trips found so far

• current path: ArrayList<Route>

• total price so far of current path

• number of stops so far of current path

• destination, budget and max number of stops for comparison

• Inside the recursive helper method:

• if current vertex is the destination  add current path to the solution set and return

• iterate over all possibilities (unmarked neighbors)

• check if you can add the neighbor to the current path (total price won’t exceed budget and total number of stops won’t exceed maximum stops)

• if so, mark neighbor, update current path, its price, and its number of stops.

• make a recursive call on the neighbor

• undo changes to current path, price, and number of stops and unmark neighbor

• mark start airport before calling solve the first timeallRoundTrips

• Use backtracking and pruning

• Define a recursive helper method: solve(current decision, current solution)

• current decision  current vertex (int or String) • current solution

• Set<ArrayList<Route>> of trips found so far

• current path: ArrayList<Route>

• total price so far of current path

• number of stops so far of current path

• budget and max number of stops for comparison

• Inside the recursive helper method:

• if current vertex is the source and stops so far > 0  add current path to the solution set and return

• iterate over all possibilities (unmarked neighbors)

• check if you can add the neighbor to the current path (total price won’t exceed budget and total number of stops won’t exceed maximum stops)

• if so, mark neighbor, update current path, its price, and its number of stops.

• make a recursive call on the neighbor

• undo changes to current path, price, and number of stops and unmark neighbor

• Don’t mark start airport before calling solve the first time