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