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.