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

Subject: [boost] [BGL] All-pair problem on a subset of vertices
From: Cosimo Calabrese (cosimo.calabrese_at_[hidden])
Date: 2010-05-17 06:43:00

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.

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.

Thanks in advance,
Cosimo Calabrese.