ing after a Removal
EC330 Applied Algorithms and Data Structures for Engineers, Spring 2019
Homework 8
Out: 4.18.19 Due: 4.30.19
1. [Single-Source Shortest Path, 8 points]
Explain how to modify Bellman-Ford’s algorithm to efficiently count the number of shortest paths (of equal weight) from a source vertex to every other vertex in the graph. What is the runtime? Explain.
2. [All-Pairs Shortest Paths, 32 points]
Consider the weight matrix D and the predecessor matrix Π output by the Floyd- Warshall algorithm. What is the most efficient way, and required runtime to use this to:
a. Detect a negative-weight cycle.
b. Determine the diameter (the length of the “longest shortest path”, counted as the
sum of the edges weights) of the graph.
c. Find a set of central vertices of the graph. That is, the set of all vertices A where the greatest distance D(A,B) to other vertices B is minimal.
st unbalanced node encountered while travelling
m w. Also, let y be the cdh.ildDoeftzerwmitihnethtehelacrogenrnected components of the graph.
x be the child of y with the larger height structure(x) to restore balance at z
3. [Trees, 8 points] uring may upset the balance of another node
The following AVL tree is provided:
ee, we must continue checking for balance until reached
62
b=y
78 88
c=x
AVL Trees
4.
a. b.
10
Draw the AVL tree resulting from inserting a node with key 52 to the above tree. Draw the AVL tree resulting from inserting the nodes with key 52 and 90 to the original tree.
44
17 50 88
48 54
62
78
[Graphs, 52 points]
The Graph class, specified in the header file Graph.h, represents a directed, weighted graph. Also provided is a sample main.cpp file, and a sample input file graph.txt. These demonstrate how we will test your code.
The input file is organized as follows:
• The first line indicates the (# of vertices) (# of edges) (type of graph)
• The (# of vertices) indicate the names of the vertices, i.e. if the (# of vertices) is 4,
then the names of the vertices are {0, 1, 2, 3}.
t r s
EC330 Applied Algorithms and Data Structures for Engineers, Spring 2019 • The rest of the lines indicate the (source vertex) (end vertex) (weight).
a. Implement the Graph class in Graph.cpp, according to the specifications in Graph.h. Do not modify Graph.h. Your code should compile with the provided files on the lab computers. Submit your Graph.cpp file.
Your program should be executed from the command-line with an input file name as argument. It should print out the output as in the sample below (listing source vertex to end vertices and their respective weights in parentheses).
0:2(13) 4(16) 5(8) 1:3(6) 5(10) 2:3(14) 5(11) 3:4(5) 5(17) 4:1(9) 5(7)
5:
b. Define and implement a public modifiedDijkstra(int source) method for the Graph class. This method should compute and print the weight and number of shortest paths from provided source vertex to all other vertices of the graph. You may assume that the graph is guaranteed to have non-negative weight edges, and that source is a vertex of the graph. The method should work for any source vertex.
In a comment at the top of your method, provide a brief description of how you modified Dijkstra’s shortest path algorithm on a directed graph with non- negative edge weights to count the number of shortest paths from a given source s to a destination node d.
Do not modify any existing code in Graph.h (you may add members as you see fit.) Submit your modified Graph.h and Graph.cpp as problem4b.zip.
Your program should be executed from the command-line with an input file name as argument. It should print out the output as in the sample below.
0:2(13) 4(16) 5(8) 1:3(6) 5(10) 2:3(14) 5(11) 3:4(5) 5(17) 4:1(9) 5(7)
5:
Shortest paths from node 0:
Distance to vertex 1 is 25 and there are 1 shortest paths Distance to vertex 2 is 13 and there are 1 shortest paths Distance to vertex 3 is 27 and there are 1 shortest paths Distance to vertex 4 is 16 and there are 1 shortest paths Distance to vertex 5 is 8 and there are 1 shortest paths