4 5 3
1 2 8
1 3 7
4 3 2
4 2 3
2 3 5
1 2
2 4
3 2
CS 3353
Fall 2022
Programming Homework 2 – The least annoying path
Due Date: 10/28/2020 (Fri) 11:59 pm.
Tony & Priscilla is a retired couple who like to travel (by driving) a lot. However, when the plan their trip
to travel from 1 city to another, their priority is a bit different from others.
Since they have retired, they have all the time in the world, so finding the shortest path from one city to
another is not their priority. However, they hate traffic and bad road conditions and other kind of
annoyances. So they would like to find a path that they don’t need to endure too strong an annoyance.
Another thing that is different is that Tony and Priscilla don’t mind traveling long distances where there
are some annoyances along the way, but they definitely want to avoid traveling on ANY road that has
high annoyance, even if it means they can reach they destination faster or has to endure such high
annoyance for just a short period of time. (Once you get to a certain age, you will understand …. )
To help them do it, they have mapped out roads between each pair of cities and give them a (floating
point number) score (> 0), where the larger the number, the more annoying the road is.
So when they plan a trip to a city where they have to go through other cities, they will always take the
path such that the most annoying road in the path is the most bearable. (Note the sum of all “annoying-
ness” of the edges along the path does not mean anything in this problem).
This can be converted to the following graph problem: given a weight graph G=(V,E). Define the
annoying-ness of a path from vertex s to vertex t to be the maximum weight of an edge among all the
edges along the path. The task above becomes that giving s and t, find the path that has the least
annoying-ness. Notice that if there are multiple paths that have the same least annoying-ness, you just
need to return one path.
Example
For the following graph:
S
A
B
C D
S T
E
F G
H
1
10
8 8
1
3
6
6
7
6
6
The least annoying path from S to T is the path S->E->F->G->H->T, with the cost 7 (along the path, the
edge with the maximum weight has cost 7). For path S->A->T has cost 10, and the path S->B->C->D->T,
the cost is 8.
Algorithm
For this problem: given two vertices s and t in an weighted undirected graph G, find the least annoying
path (i.e. the path such that the weight of the maximum edge along the path is minimized.)
Find the MST of G, and then find the path from s to t ONLY using the edges on that MST.
In this homework, you are to implement a solution to this problem using this algorithm. You have the
choice of how to implement the MST, and how to find the path from s to t on the MST.
Program specification
You are to implement following class called MyGraph. It represents an undirected graph with weights on
each edge. You must implement the following methods:
Methods:
• Constructors:
o MyGraph(int n): Create a graph with n vertices. The vertices are labelled 1..n
o MyGraph(const MyGraph& g): Construct a new graph that is a copy of g
• Methods
o bool AddEdge(int a, int b, float w): Add an edge between vertex a and b, with weight w.
If the edge already exists or a vertex is not on the graph, do nothing and return false.
Otherwise (addition is successful) return true.
o void Output(ostream& os): Output the graph to the ostream& specified. Your output
should have the following format:
▪ The first line print the number of vertices.
▪ Each subsequent line prints an edge. It should print three numbers: the two
vertices associated with the edge (print the vertex with the smaller number
first), and the weight of the edge. You should have one space character
etween the numbers, and no space at the end. You can order the edges
whatever way you want.
o pai
vecto
int>, float> HW2Prog(int s, int t): This is the main function that you have to
implement for this homework.
▪ The function will find a least annoying path from s to t. The return will be a pair.
The first item of the pair (vector) denotes the path from s to t. The first item of
the vector should be s and the last one should be t, and the vector is the order
of the vertices on the path from s to t. The second item (float) denote the actual
annoyance (i.e. the weight of the edge that has maximum weight on the path). .
You will be given a driver program, hw2main.C. The program will read in a file containing a graph,
together with the pairs of vertices where the least annoying path is wanted. It will then run the main
program and output the result.
The input file format is as follows.
• The first line contains three integers, which represent the number of vertices (n) of the graph,
the number of edges (e), and the number (c) of least annoying path to be found.
• The next e lines contain the edges of the graph. Each line has three numbers, the first two
number represents the two vertices, where the third represent weight of the edge.
• The next c lines contain the pair of vertices where the least annoying path is needed. Each line
has two numbers, s and t respectively.
You can assume the input file is co
ectly formatted. If not, you are not responsible.
Task
You should implement all the methods in the class. Note the following:
• You are allowed to create extra methods for the graph class.
• You are allowed to create extra classes to be used.
• You are free to choose any implementation of the graph you prefer (adjacency matrix, adjacency
list etc.)
• You can also choose which algorithm you use (Kruskal, Prim, etc.)
What to hand in
You have to hand in two files (zipped into a .zip file) (-20 if you hand in more than two files):
• One file contains all your source code (including your implementation of MyGraph class, but
without the code for hw2main.C). You should call your file MyGraph.h
• One file containing a description on how you implement your algorithms for HW2Prog method.
Include your choice of how your graph is being represented and what algorithm you use.
Grading
For this homework, full mark is 100.
You get 95 points for successful implementation of the algorithm. Partial credit will be given.
For all programs that is successful, I will run more tests and measure the running time of the program.
Those who run fastest will get extra score as follows:
Rank Bonus
1 60
2 45
3 35
4-6 25
7-10 20
XXXXXXXXXX
XXXXXXXXXX
26-35 5
o If there are ties the bonus will be averaged. For example, if there are two people tied for
second, each of them will get (45+35)/2 = 30 bonus points. Notice that we measure ties not by
exact time, but that the difference in running time is small enough.
o There will be multiple test cases with various size graphs and solutions. Each program will be run
multiple times and the average of the time will be used. Different test cases will be comparing
independently (so we do not add the run time of 5 cases together). Notice that some test case
may contains up to 1000s of vertices and 100000s of edges.
Bonus 2
You get 15 extra points if you can prove that the algorithm is co
ect. You should include an extra pdf file
(named proof.pdf) that describe your proof. (Hint: contradiction is probably the easiest way to do it).
Example
Suppose the input file looks like this
4 5 3
1 2 8
1 3 7
4 3 2
4 2 3
2 3 5
1 2
2 4
3 2
The main program will first create a graph of 4 vertices, with the following 5 edges:
Then you should find the least annoying path of the following:
• From 1->2 : path 1->3->2, weight 7 (notice that 1->3->4->2 is also a solution, your program can
output either of those).
• From 2->4 : path 2->4, weight 3
• From 3->2 : path 3->4->2, weight 3
For your HW2Prog(int s, int t) function in this case
• HW2Prog(1, 2) will return the vector [1 3 2] and the number 7
1 2
4 3
8
7 5 3
2
• HW2Prog(2, 4) will return the vector [2 4], and the number 3
• HW2Prog(3, 2) will return the vector [3 4 2], and the number 3