Path matrix

Question

given a graph G,a matrix Pk represent  a matrix in which each entry pk[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 Pk[i][j] is termed as Gk .

Gk 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 Gk if the graph G is represented by using  adjacency list and what will be the time complexity to do it ??

Answer 1

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.

Comments

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.

---

ya i am not updating the adjency list . becuase i need not to . i will store teh info extracted rom adjency list in an array and then computing as floyd warshell do .and u may again rewrite the result to the adjency matrix.

---

...did nt get it..can u write the algo step by step because if u r using the array to to store nd then using the warshall algo then it should be done in 0(v^3) ...  nd i had expected some aglo  where we will not use array