[R] Igraph library: How to calculate APSP (shortest path matrix) matrix for a subset list of nodes.

[Moshe Olshansky]

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 <barupal at gmail.com> wrote:

> From: dinesh kumar <barupal at gmail.com>
> Subject: [R] Igraph library: How to calculate APSP (shortest path matrix) matrix for a subset list of nodes.
> To: r-help at 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 at 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.