Re: [boost] [BGL] All-pair problem on a subset of vertices

Subject: Re: [boost] [BGL] All-pair problem on a subset of vertices
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-05-17 10:51:56

On Mon, 17 May 2010, Cosimo Calabrese wrote:

> Hi to all,
>
> if we want to find the shortest distance between *every* pair of vertices in 
> a graph, we can use the Jonson's or Floyd-Warshall's algorithm, obtaining a 
> NxN matrix of distances, where N is the total number of the graph's vertices.
>
> The problem is: how can I do if I don't need the distance of *every* pair of 
> graph's vertices, but I'm interested in only a subset of vertices? In other 
> words, I would to obtain a MxM matrix, where M<N. In every case, I'm not 
> interested in path from the pairs, but only in the distance.
>
> My solution is to execute M times the Dijkstra algorithm from every vertex of 
> the subset, and to abort every exploration when I've founded the Mth vertex 
> of the subset.

I'm not sure there is a reasonable way that's faster than this in the 
general case.

> Are there something of more efficent? My graphs contain approximately 12 
> millions of vertices, but I'm interested in a subset of 10.000 vertices.

I doubt it.  You can try looking up "multi-source shortest paths" and see 
if there are any algorithms that would help.  If you find one, I might be 
able to help you implement it in terms of BGL.

-- Jeremiah Willcock