Re: [Boost-users] BOOST graph- shortest path which including a nodeset?

From: Johan Råde (rade_at_[hidden])
Date: 2006-12-26 03:49:02

Terence Wilson wrote:
> 
>> -----Original Message-----
>> From: boost-users-bounces_at_[hidden] [mailto:boost-users-
>> bounces_at_[hidden]] On Behalf Of Johan Råde
>> Sent: Monday, December 25, 2006 2:42 PM
>> To: boost-users_at_[hidden]
>> Subject: Re: [Boost-users] BOOST graph- shortest path which including a
>> nodeset?
>>
>> Terence Wilson wrote:
>>> 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)
>> 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.