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

From: Johan Råde (rade_at_[hidden])
Date: 2006-12-25 17:42:06

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