Hey Thanks, I need algo of complexity same as BFS i.e O(m+n). I think we need to use BFS with some twiks. and it is undirected graph.
Raj On Sep 16, 7:54 pm, "daizi sheng" <[EMAIL PROTECTED]> wrote: > you mean the number of shortest paths in G from give vertexes A & B ( A to > B) > let me formulate the number as this > > f(A,B,len) > > where A is the src, B is the dst and len is the length of the shortest path > > it is easily to be derived out that > f(A,B,len) = \sum_{C is A's neighbor} f(C,B,len-1) > > also the base is f(B,B,0) = 1 > > then the complexity of this algorithm is? > > there are only at most n*n states for all possible A,B,len (because if we > know A & B we should have already known len) > > and to caculate f(A,B,len) we need to check all neighbors for A, that's d(A) > also we at most check len times (so at most n times) > > then we totally check (sun of all d(a)) * n = 2mn (m is the number of edges) > > and so the algorithm is O(n^3 * m) > > but this is not the best algorithm, we can even get an algorithm with same > bound of shortest path algorithm > > firstly, perform a shortest path algorithm to get all dis(C,B) where B is > the dest and C is any vertex (including A) > we construct a direct graph like this > > an edge connect X to Y iff dis(X,B) = dis(Y,B) + 1 > > you can prove that this graph is a direct acyclic graph and every path from > A to B in this graph is shortest path in the original graph > and any shortest path from A to B in the original graph is a path in this > graph > > now what you need to do is calculate the number of shortest path from A to B > in this new graph. > > but this is a direct acyclic graph, so very easy,:) > > hope this can help you > > 2007/9/17, Raj <[EMAIL PROTECTED]>: > > > > > > > what is the algo for finding the number of shortest paths in Graph G. > > It is unweighted graph.- Hide quoted text - > > - Show quoted text - --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---