Cosc 2P03 Fall 2017
Assignment#4
(Due date for assignment is Monday, Nov. 20th
4:00 p.me, Late date Thursday Nov. 23rd, 4:00 p.m.)
Objective
To Heaps and graphs.
Dijkstra's Algorithm
Implement Dijkstra's algorithm. Find the shortest path from Vo to
all other nodes in the graph G. G is defined by a set of ordered
triples in the form (u,v, weight). The graph is given by the data file, where V0 is defined by the
first triple in the list.
Your solution should make use of classes. As a requirement you
should create 1 class which implements a priority queue as a Heap.
PQ operations should include, isEmpty, Enter, and Leave.
The graph G will need to be stored in an appropriate adjacency list
(an assignment requirement). Create a class which implements an
adjacency list appropriate for this algorithm. Implement functions
which allow for querying the list. E.g. For each w adjacent to v.
Output should consist of a neatly formatted table with the following
headings, v, known, dv, pv.
Note: that when entering a vertex in to the PQ, we need to enter the
weight as well as the vertex number. This implies an object. Thus
create a Node class representative of the data values needed.
Suggested Plan of Attack
- This assignment is best completed in stages. Dijkstra's
algorithm is fairly easy to implement once all the pieces are in
place.
- Consider first creating the PQ class and testing it with the
appropriate Node class.
- Create the Adjacency list class. Giving it the ability to read
in the graph, print it out, do searches as appropriate.
- Implement Dijkstra's algorithm
- the table can be a matrix.
- you will need the ability to print the matrix.
- Compare your results with your class mates results. Since
everyone is using the same graph, then all should get the same
result.
Note: a test harnesses is not part of the assignment and can be
omitted, but is required to give peace of mind during the
development phase. This is not a hard assignment if one completes
this in an orderly systematic process of develop a little and test
allot.
Submission Requirements:
- Cover Sheet completely filled out, available
from: "http://www.cosc.brocku.ca/forms/cover"
Note: your assignment will not be marked unless one is submitted
with the assignment on the assignment due date.
- Commented and properly documented source code
listing, use Java Doc style.
- Listing of any input you used to test your program.
- Listing of your output which reflects the input.
- Source code is to be Java.
- Be sure to hand in a hard copy of the above and a soft copy as
directed below.
- Electronic
submission, run the script "submit2p03" from sandcastle.
- Statement on coversheet with following information.
- Platform, e.g. Mac, PC, Commodor 64, my Java enabled wrist
watch.
- Compiler Version, e.g. Java 1.7, Java 1.81 e.g.
Good Luck