Homework 4 Solution

    1. Purpose: Learn about articulation points, bridges, biconnected components, and Euler tours. Please solve
        a. Problem 22-2 a-e (3 points each)
        b. Problem 22-3 a (6 points) on page 623.

2. Purpose: Reinforce your understanding of minimum spanning trees (8 points). Please solve problem 23-4 on page 641. You do NOT have to describe the most efficient implementation of each algorithm.

3. Purpose: Reinforce your understanding of Dijkstra’s shortest path algorithm, and practice algorithm design (16 points). Suppose you have a weighted, undirected graph G with positive edge weights and a start vertex s.

a) (6 points) Describe a modification of Dijkstra’s algorithm that runs (asymptotically) as fast as the original algorithm, and assigns a binary value usp[u] to every vertex u in G, so that usp[u]=1 if and only if there is a unique shortest path from s to u. We set usp[s]=1. In addition to your modification, be sure to provide arguments for both the correctness and time bound of your algorithm, and an example.

b) (10 points) Implement the algorithm described in a). As you can see in the code framework provided (DijkstraFramework), Dijkstra.py/java file has a method: Dijkstra_alg. The method has an input parameter list (n, e, mat, s), where n = number of vertices of G, e = number of undirected edges of G, mat = an e x 3 matrix that defines the edges of G, and s = the source vertex of Dijkstra’s algorithm. Assume the vertices of G are numbered 1…n. In mat each row consists of three integers <u, v, weight>. Here, u and v define the edge (u,v), and weight is the corresponding edge weight. The method returns an n x 2 matrix, where the ith row contains the path length and the usp value for the shortest path between source and vertex i for i {1, …n}. More detailed examples (that refers to the first two test cases) are given below. You can create additional methods if required but do not change the name of existing methods and any existing code - points will be cut if you do. To avoid loss of marks, you should use basic arrays to implement the priority queue in Dijkstra’s algorithm, and not use any packages. You can code this in either Java or Python. Another file DijkstraTest.py/java has been provided which tests your code for various inputs. You need to test your code on VCL using this file (instructions for VCL setup and test are can be referred from readme file provided in last homework). Please only submit the file Dijkstra.py/java and not the test file. Your code will be checked on VCL by us automatically using the provided cases, plus some (unknown) inputs. To avoid loss of marks please make sure that all provided test cases pass on VCL by using the test file.

Some examples: 
Testcase1
Input values 

n = 5, 
e = 6, 
mat = [[1, 2, 9], [1, 3, 6], [1, 4, 5], [1, 5, 3], [3, 2, 2], [3, 4, 4]],
s = 1 

Output
   Ans = [[0, 1],  Shortest path weight source to vertex 1 is 0, usp is 1
               [8, 1],  Shortest path weight source to vertex 2 is 8, usp is 1
               [6, 1],  Shortest path weight source to vertex 3 is 6, usp is 1
               [5, 1],  Shortest path weight source to vertex 4 is 5, usp is 1
               [3, 1]]  Shortest path weight source to vertex 5 is 3, usp is 1

All shortest paths originating from source vertex 1 are unique, and the corresponding usp value is 1.

Testcase2: 

Input values                                                                                                 
n = 5, 
e = 5,
mat = [[1, 3, 2], [1, 5, 3], [2, 5, 3], [4, 1, 1], [4, 2, 1]] 
s = 4

Output
    Ans = [[1, 1],  Shortest path weight source to vertex 1 is 1, usp is 1
               [1, 1],  Shortest path weight source to vertex 2 is 1, usp is 1
               [3, 1],  Shortest path weight source to vertex 3 is 3, usp is 1
               [0, 1],  Shortest path weight source to vertex 4 is 0, usp is 1
               [4, 0]]  Shortest path weight source to vertex 5 is 4, usp is 0

There are two shortest paths of length 4 from source vertex 4 to vertex 5. Therefore, the usp value of fifth row is 0. All other shortest paths originating from vertex 4 are unique, and therefore the corresponding usp value is 1.