Algorithms

Suppose we are given an undirected graph G=(V,E) in an input file which has the number of nodes and the matrix. We want to preprocess the graph so we can quickly answer a query of the form:Path(i,j) that returns YES if there is a path from vertex to vertex j in G, and NO if there is no path. Your goal is to be able to answer Path(i,j) for any pair i, j in O(1) time. a) A simple way to solve this problem is to construct an n × n matrix P such that P[i, j] = 1 if there is a path from i to j, otherwise P[i, j] = 0. Describe how to construct such a matrix P.(for this part, don’t worry about the fastest method). Give the complexity analyses of your method. b) We now want an improved scheme to answerPath(i,j) that only uses O(n) extra space to store the information we use to answer in O(1) time. In addition, we want our preprocessing to be fast. i) Describe how to do the preprocessing in O(m + n) time (and using O(n) extra space. ii) Describe how to answer a Path(i,j) query in O(1) time for your method. Provide details on the design of your algorithm. Explain how your algorithms work step by step andv answer the questions above. Program call: mySM inputfile Input format: First you will have a number which denotes the number of nodes (n) and second an (nxn) matrix in the file.