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.
Dear sir,
I am strong in C++/java programming especially in algorithm implementation. I am proficient in Graph theory and algorithms. I have deep insight into Floyd-Warshall, Dijkstra, Breadth First Search, Depth First Search, Maximum Flow, Max Match and etc algorithm and I have implemented them Based on your requirement I think I can solve the problem by Floyd-Warshall and Depth First Search algorithms and I have both implemented them and I can do it with high quality in a short time. I can show you my past code.
Wait for your response
Thank you
BR
Hi. I am good at Algorithm Design/Analysis and Data Structure. I have experience in C# too. Code and description are available. I can handle it, please check Inbox. Best regards.
So you just want all of this written in a text file right? The complexity analysis of how to make the nxn matrix which tells if path(i,j) exists. and for part b, you want a memory efficient method and also how to do that in O(m+n) time? btw what's m? As for the O(1) access time, well if it's like the matrix, you just need a simple memory access to find out the answer.
Correct me if I am wrong about anything and check the private message to see what i have to offer