Assignment 3: Shortest Paths and
Minimum Spanning Trees
COMP2003J: Data Structures and Algorithms 2
Weight: 50% of final grade
Document Version: 1.0
Introduction
The goal of this assignment is to analyze and program some graph algorithms
and visualize them. This assignment includes three tasks.
Task 1 – Shortest Paths
- (5%) A program called DijkstraLabeller.java tries to label the shortest
path for a given weighted graph with a starting vertex by harnessing
Dijkstra’s algorithm. It may work but not be perfect. Please study this
implementation carefully and point out its weakness(es), which can be
such as lacking enough information in returned objects, low efficiency
etc. When you find out a point, you need to make an in-depth analysis.
For example, assume that this implementation has a low-efficiency
issue; you need to specify where they are from, their time complexity,
etc. - (10%) Based on the analysis from the previous step, you need to reimplement
this solution to solve these issues. You need to create a
new java class named DijkstraLabeller2.java within the package
dsa.algorithms. If needed, you can create a few other classes. For
example, as we mentioned in our lecture, if you want to use an
adaptable priority queue, you may need to create a new interface and
its implementation as well. In your solution, you can use java built-in
data structures, such as Map, List etc. However, a graph and its edges
and vertices must be represented by the classes provided within the
assignment. - (5%) Create a test class named TestDijkstraLabeller.java to check
that your solution is correct and make comparisons with the previous
solution.
Task 2 – Minimum Spanning Trees - (5%) A program called KruskalLabeller.java manages to label the
minimum spanning tree in a given graph by utilizing Kruskal’s
algorithm. Similar to Task 1, please study this implementation carefully
and point out its weakness(es), particularly in terms of its efficiency. - (10%) Based on the analysis from the previous step, you need to reimplement
this solution to solve these issues. You need to create a
new java class named KruskalLabeller2.java within the package
dsa.algorithms. If needed, you can create a few other classes. For
example, you may need to implement Union-Find structure. In your
solution, you can use java built-in data structures, such as Map, List
etc. However, a graph and its edges and vertices must be represented
by the classes provided within the assignment. - (5%) Create a test class named TestKruskalLabeller.java to check
that your solution is correct and make comparisons with the previous
solution.
Task 3 – Visualization
(10%) Visualization can help us to better understand graphs and examine our
graph algorithms. This task requires you to study the existing java-based
techniques for graph visualization and choose a suitable one to implement a
solution to visualize the graphs used in your testing in Trask 2 and Task 3 and
demonstrate the process of Dijkstra’s algorithm and Kruskal’s algorithm.
Instructions
• Download the file Assignment3-Source.zip from Brightspace. The
contents of this file include DijkstraLabeller.java and
KruskalLabeller.java and all their dependent classes.
• When you study the weaknesses of the existing implementations, you
need to record these weaknesses and your analysis in your report.
• In your solutions of Task 1 and Task 2, a graph must be represented
by IGraph, and its vertices and edges must be represented by IVertex
and IEdge, which are defined in dsa.iface package. a Graph
implementation: EdgeListGraph is provided in dsa.impl package,
you should use it in your testing to hold your graph data.
• You can design your own returned data type to hold any data you need
for the next step to visualize graphs.
• This assignment requires you to do some independent research
outside of what is directly covered in the lectures. For example, two
chapters in Goodrich and Tamassia’s book are suggested to read, i.e.,
Chapter 9.5 Adaptable Priority Queues, Chapter 14.7.3 Disjoint
Partitions and Union-Find Structures. You can learn the solutions
provided by these chapters and then make your own solutions.
• When testing your implementation and making comparisons, you
should compare their efficiencies at different graphs and record the
results and analyze them in your report.
• In the task of visualization, you can use any java-based components.
• You should summarise the studies for graph visualization and briefly
depict your solution. It is essential to put critical screenshots of the
visualization produced by your program into the report.
Submission
This is an individual assignment. Therefore, all code and the report
must be written by yourself. Assignment 1 contained some advice
about avoiding plagiarism in programming assignments.
• Submit a zip file to Brightspace, which should include all java files,
libraries, and data used in your project. All code should be wellformatted
and well-commented to describe what it is trying to do.
• Submit a pdf report to Brightspace. This report should be a humanreadable
document (i.e., do not simply include code). In your report, it
is recommended to have the following essential topics, but not limited:
o Record the weaknesses of the existing implementations and
provide your in-depth analyses.
o Depict any tricks (novel or different ideas) used in your solution.
o Document the testing strategies and record results and provide
your analyses.
o Include a short literature review about Java-based graph
visualization.
o Depict your visualization solution.
o List newly added java classes, and describe their functionalities.
• The pdf file of your report must be submitted as a separate file, i.e., it
cannot be compressed into the zip file with your code or data, for the
purpose of originality checking.