代写Dijkstra算法，寻找复杂权重图的最短路径。
Project Description
This project has three objectives: 1) for you to implement Dijkstra’s shortest
path (least cost) algorithm, 2) to give you an experience similar to that of
performing real-world maintenance work on existing applications, and 3) to
show you some production-like use of the object-oriented ideas we have been
discussing.
Typically developers spend 60 percent of their time performing maintenance
work on existing applications. Unlike typical classroom assignments,
maintenance work seldom involves elegant, idealized structures, is never code
you wrote, typically sits in the middle of applications so large that you can
never afford to read every line of the app before you start work, often
involves code which is shared between multiple applications, might come (in
the best shops) with lots of developer and test support infrastructure, and is
seldom supported with precise and clear instructions. In fact, you might have
drawn this code because the last person to have worked it left the company
before taking time to writing the related documentation.
For this project you play the role of a (new to the project) employee who will
complete a partially finished new “shortest path” feature in two different
graph-based applications: Maze and Explore. Maze is a very small application
that builds graphs. Explore builds terrain maps on an extended version of the
same graph used by Maze. Explore is a much larger application (though still
small compared to most commercial applications) , and is currently broken
because another feature change (revising the way that Explore parses input
files) is not quite finished.
Specifically, you must supply code at the “//TODO:” markers in
- Maze’s PathFinder.findPath() method an
- Explore’s TerrainLoader() class, and
- uncomment a line in Explore’s TerrainBoard.paint() method.
This work will require that you:
- write your own implementation of Dijkstra’s shortest algorithm using Maze’s
existing Graph, Heap, and Stack code. (We will variously call this “the
solver” or Pathfinder class.) - Insert your solver code into a presently stubbed method in the already
working and otherwise complete Maze application (PathFinder.findpath()). - Complete three or four parsing methods in one class in Explore, using some
classes especially designed for the task (a special Scanner, for example).
With the specialized classes, each of these methods should be just a few lines
long. - Uncomment a line in Explore to activate its new shortest path feature
(which uses a sub classed version of the same graph class as Maze, thus your
solver should be just what is needed in both applications.)
Like many real employers, we assume you are a quick study, and rather than ask
a senior developer to sit with you and guide you through the task, we have
collected, for you, all the existing documentation associated with these two
applications. We assume that somewhere in that documentation or in the source
code, you will find what you need. (Just don’t spend too much time trying to
understand all the code in Explore, or you’ll miss the ship date.) Unlike most
employers, we will at least point you to the existing developer infrastructure
and give some advice about when and how to use them.
We will supply two documentation packages via BlackBoard, one for Maze and one
for Explore.
You will find related requirements mostly in the Javadoc within the source
code or in the developer notes in the respective documentation packages. If
you have questions, pose them first on Blackboard.
The documentation packages are divided into three sections: end user
documentation, developer documentation, and supporting background material .
These documents are similar to, but more in some ways more generous, and
generally more targeted than the information that might be available to you as
a new employee in a typical software company. Your goal in reading this
material should be to better understand the application and how your work fits
into it. Remember, some of the specific instructions in the User Documentation
are meant to apply to end users only; you are a developer.
It is unreasonable to expect every line of these packages to relate only to
some specific, separately graded task required of you. It is equally
unreasonable to think you can do a good job without reading anything but this
project description document and the code.
You should follow this work plan:
- Get Maze running without a solver.
- Build a solver using Maze and supplied drivers, demo data, tests etc. as your development harness.
- Complete the TerrainLoader for Explore. Use the supplied Junit driver initially, because it does not require a full working app. Add code for and test each new feature description section separately.
- Add your solver and the TerrainViewer, to the test driver. Uncomment the wiring that uses the solver.
The Templates
The “templates” will be supplied in two different zips, one for Maze and one
for Explore. You should work on Maze now. When the Explore templates are
available, you should copy the source into a new project and then copy the
“shared” package from your working Maze project into the appropriate place in
the new Explore code. Do not attempt to import either project into the other.
We will not make any allowances for “accidents.” If you destroy your work at
some point in this project, we will make no accommodation in your grade. You
are responsible if your work is lost because you haven’t observed necessary
backup protocols.
Submission
You will submit a single project containing both applications. You are
required to include, in your submission, the source code for each of the
classes: You need to write proper documentation with Javadoc for any
additional helper methods you might define. You must not make any change to
Graph. Your solver should operate on the graph only through the Bare
interfaces.
Write your class so that its package name is hw5. Your source files (.java
files) will be placed in the directory, as defined in the Maze and Expire
template files. Be sure to insert your name after the @author tag in the
PathFinder class and the TerrainLoader class. Your zip file should be named
Firstname Lastname HW5.zip. You may submit a draft version of your code early
to see if you have any submission problem with Blackboard Learn. We will grade
only your latest submission.
