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