Terence Wilson wrote:
-----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users- bounces@lists.boost.org] On Behalf Of Johan Råde Sent: Monday, December 25, 2006 2:42 PM To: boost-users@lists.boost.org Subject: Re: [Boost-users] BOOST graph- shortest path which including a nodeset?
What I need is a version of Dijkstra's shortest path where the path includes a specified set of nodes. Does this exist? Say that you want find the shortest path from P_1 to P_n (in a graph G)
Terence Wilson wrote: that passes through P_2, P_3, ..., P_(n-1) in any order.
Form a new graph, H, with exactly n vertices Q_1,...,Q_n, exactly one edge from Q_i to Q_j for each i and j, and where the length of the edge from Q_i to Q_j in H equals the length of the shortest path from P_i to P_j in G.
Then the original problem, in G, is equivalent to the problem of finding the shortest path in H from Q_1 to Q_n that passes through every vertex of H.
That problem is very similar to the Travelling Salesman Problem (TSP) for the graph H. That is an NP complete problem, meaning that there is no fast algorithm for finding the optimal solution. If n is not too large you can do an exhaustive search: try each permutation of Q_2, ..., Q_n-1. If that is too slow, then you must use some heuristic algorithm, that gives a good but not always optimal solution. There is a good discussion of TSP, including links to sites with code, in Wikipedia.
--Johan
But what I am trying to find is the shortest path in G, from Pi to Pj which includes but does not necessarily *exclusively* consist of {Px1, Px2,...,Pxn).
Your reframing of the problem solves the exclusive path case.
Once you have solved the problem for H, you get the solution for G as follows: If the solution in H is the path Q_1, Q_a, Q_b, Q_c, ...,Q_z, Q_n then the solution in G is the shortest path from P_1 to P_a, followed by the shortest path from P_a to P_b, followed by the shortest path from P_b to P_c, ..., followed by the shortest path from P_z to P_n.
In other words, it's TS without the requirement to visit every node and start & finish at the same node. And yes, it's probably NP-Complete and not solvable for large n. Do you know of any Boost Graph algorithms to solve this?
No. Or perhaps a fast algorithm for approximate solutions? There are lots of them, and there is plenty of info on the web.