Description
Task:
Step 1:
Add to ALGraph.java an implementation of depthFirstSearch and bestSearch. Use the Dijkstra algorithm as the implementation for bestSearch.
Step 2:
Add to the graph in TestGraph an edge from Detroit to Pittsburgh with a distance of 400.
Modify the TestGraph to print the path results from breadthFirstSearch, depthFirstSearch, and bestSearch for paths from Philadelphia to Detroit and Fort Wayne to Toledo.
Step 3:
Create a new test program, TestGraph2, using the same graph of step 3, only use a Road object for edges. The Road object must have a distance and a speed limit attributes. Use the same distances, only use 80 as the speed on the path from Pittsburgh, Cleveland, Columbus, Indianapolis, Fort Wayne, to Chicago, and 25 for all other edges. Then find and print the breadthFirstSearch, depthFirstSearch, bestSearch using distance, and bestSearch using time for the path from Philadelphia to Chicago.
Step 4:
Create a new test program, TestGraph3 for the directed graph in Figure 10.26 (shown below). Then find and print the breadthFirstSearch, depthFirstSearch, bestSearch for paths from 0 to 4 and from 1 to 0.
Bonus
Provide an aStarSearch method. This method has the same arguments as the bestSearch except uses the A Star algorithm to determine the best path. For this problem a City class must be defined. A city will hold the city name along with coordinates. Use the straight line distance between two cities (based on the city coordinates – that is the square root of the sum of square of delta x and square of delta y) as the heuristic guiding the A Star algorithm. Use the coordinates on the following graph:
Run the aStarSearch for “Toledo” to “Fort Wayne”.
