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

From: Terence Wilson (tez_at_[hidden])
Date: 2006-12-25 18:46:13

> -----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.

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? Or perhaps a fast algorithm for approximate solutions?

Thanks for responding.