Boost logo

Boost :

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at