i dont know thw answer.

The Gateway to Computer Science Excellence

0 votes

given a graph G,a matrix P_{k }represent a matrix in which each entry p_{k}[i][j] represent the shortest path from node i to node j in G which uses only nodes 1,2,3.............k-1 .The corresponding graph formed by using matrix P_{k}[i][j] is termed as G^{k}^{ }.

G^{k }can be calculated by taking the square of adjacency matrix of G k times and replacing each multiplication and addittion operation by AND and OR operation.(concept of warshall's algorithm of unweighted graph) .now my question is how to find G^{k} if the graph G is represented by using adjacency list and what will be the time complexity to do it ??

0 votes

what i think is O(v^4) may be the answer.

first of all the data is in adhency list like this

to compute inital distances time taken will be o(v3) as suppose i am calculating a then for the idstnce to b i have to seach all the adjency nodes of a . which may be v in worst case. and for c again and so v time i have to search v nodes which is v2 and i have to do so for v times . so v3. now when i have calculated the initial matrix distances. and such v matrix have to be calculated . else u may think this way .

now for distance of a to c through b we will hav to first find the distance from a to b which is v time and then from b to c which is also v time now . and then compare with the inital distances . so time complexity will be (v+V+1)=O(v) this is just one entry . such v^2 nodes have to calculated in worst case i.e. complete graph . and such v passes will be made so v*v^2*v=O(V^4).

answer may be wrong . what is the answer.

0

let say we have to find a path of length 4 from a to b then how we will do it??In ur method u r not updating ur adjacency list so if we need to calculate a path of length n from a to b we will need the value of a path of length n-1 which does nt uses a specific node and on the basis of this value we generally decide the path of length n exists or not..

i dont know thw answer.

i dont know thw answer.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,339 answers

198,449 comments

105,204 users