It is O(|V|+|E|) to calculate unweighted shortest paths from one vertex to all others. It is indeed O(|E|*log|V|) if you have a weighted graph. But both of these should be reasonable for |V|=25000 and 500 sources, you just need a fair amount of memory.
For the details see ?shortest.paths. Gabor On Sun, Aug 24, 2008 at 11:06:08PM -0700, Moshe Olshansky wrote: > I was too optimistic - the complexity is O(E*log(V)) where V is the number of > nodes, but since log(25000) < 20 this is still reasonable. > > > --- On Mon, 25/8/08, Moshe Olshansky <[EMAIL PROTECTED]> wrote: > > > From: Moshe Olshansky <[EMAIL PROTECTED]> > > Subject: Re: [R] Igraph library: How to calculate APSP (shortest path > > matrix) matrix for a subset list of nodes. > > To: r-help@r-project.org, "dinesh kumar" <[EMAIL PROTECTED]> > > Received: Monday, 25 August, 2008, 3:27 PM > > As far as I know/remember, if your graph is connected and > > contains E edges then you can find the shortest distance > > from any particular vertex to all other vertices in O(E) > > operations. You can repeat this procedure starting from > > every node (out of the 500). If you have 100,000 edges this > > will require about 100,000*500 = 50,000,000 operations > > (times a small factor) which is very reasonable. > > > > > > --- On Mon, 25/8/08, dinesh kumar <[EMAIL PROTECTED]> > > wrote: > > > > > From: dinesh kumar <[EMAIL PROTECTED]> > > > Subject: [R] Igraph library: How to calculate APSP > > (shortest path matrix) matrix for a subset list of nodes. > > > To: r-help@r-project.org > > > Received: Monday, 25 August, 2008, 8:00 AM > > > Dear R Users, > > > > > > I have a network of 25000 total nodes and a list of > > 500 > > > node which is a > > > subset of all nodes. Now I want to calculate the APSP > > (all > > > pair shortest > > > path) matrix only for these 500 nodes. > > > I would appreciate any help. > > > Thanks in advance > > > > > > Dinesh > > > > > > -- > > > Dinesh Kumar Barupal > > > Research Associate > > > Metabolomics Fiehn Lab > > > UCD Genome Center > > > 451 East Health Science Drive > > > GBSF Builidng > > > University of California > > > DAVIS > > > 95616 > > > http://fiehnlab.ucdavis.edu/staff/kumar > > > > > > [[alternative HTML version deleted]] > > > > > > ______________________________________________ > > > R-help@r-project.org mailing list > > > https://stat.ethz.ch/mailman/listinfo/r-help > > > PLEASE do read the posting guide > > > http://www.R-project.org/posting-guide.html > > > and provide commented, minimal, self-contained, > > > reproducible code. > > > > ______________________________________________ > > R-help@r-project.org mailing list > > https://stat.ethz.ch/mailman/listinfo/r-help > > PLEASE do read the posting guide > > http://www.R-project.org/posting-guide.html > > and provide commented, minimal, self-contained, > > reproducible code. > > ______________________________________________ > R-help@r-project.org mailing list > https://stat.ethz.ch/mailman/listinfo/r-help > PLEASE do read the posting guide http://www.R-project.org/posting-guide.html > and provide commented, minimal, self-contained, reproducible code. -- Csardi Gabor <[EMAIL PROTECTED]> MTA RMKI, ELTE TTK ______________________________________________ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
