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.
