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

Subject: Re: [boost] [BGL] All-pair problem on a subset of vertices
From: Cosimo Calabrese (cosimo.calabrese_at_[hidden])
Date: 2010-05-18 04:44:33

Jeremiah Willcock wrote:
> 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.
> 

Well, I work on a road network, and my main target is to solve the TSP 
problem. So I need the all-pair distances of the "visits" that the 
salesman must do. The graph I use is sparse, generally 3-4 edge for 
every vertex. The edges are not abstracts like the general graphs, but 
they have a real geometry and directions, that may helps to solve the 
non-general problem.

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

Thanks for your help, I'll try it.
Cosimo Calabrese.