[BGL] All-pair problem on a subset of vertices
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.
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
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.
participants (2)
-
Cosimo Calabrese -
Jeremiah Willcock