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
-~----------~----~----~----~------~----~------~--~---
