2007/9/18, Raj <[EMAIL PROTECTED]>:
>
>
> 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.
oh you do not got my idea
I mean the complexity of the algo is same with shortest path algorithm
and in unweighted graph, it is same with bfs,:) i.e. O(m+n)
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 [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
