Question

1. Consider the following scenario:

The Colonel Motors Corporation of Frankfort, Kentucky has produced a new line of vehicles which require chicken droppings for fuel. Because of this unusual fuel requirement, there are only certain fueling stations in the country where the vehicles can be refilled. Thus, to get from one place to another, an owner must plan a route that ensures that he can get refills along the way. The Colonel Motors Corporation has hired Professor Sanders of the Kentucky Institute of Technology as a consultant to prepare an online route-finding service. To use the computerized service, an owner will enter the driving range of his vehicle (the distance the vehicle can go on a single fill-up), the "distance to empty" (the distance the vehicle can go with the fuel that's now in the tank), his/her initial location (source), and his/her desired destination. The service will either respond with a shortest route from the source to the destination such that the owner never runs out of fuel, or it will deem that no such route exists. Model the professor's problem in terms of a weighted, directed graph in which streets are edges, intersections are vertices, and some intersections have fueling stations, and design an efficient algorithm to solve it. Assume that a driver's source and destination are also at intersections.

2. Choose an appropriate problem solving technique:

a. Select your favorite programming language such as C, C++, or Java. In that language, write, implement, and test an algorithm using the problem solving technique that you chose.

b. Analyze your implementation using either order notation analysis or empirical analysis.

c. You must prepare a separate page providing the instructions to compile and execute your program, such as the development environment (e.g., Visual Studio). If no such information is provided, and your program fails to build and run, points will be deducted, as appropriate.

TASK:

1. Java code

2. Discussion of your problem solving technique and why chosen

3. Algorithm (pseudocode, source, etc.)

4. Correctness

Answer 1