## hortest path from s to t with which includes all subset

Moderator: Board moderators

nicoletsg
New poster
Posts: 15
Joined: Sat Dec 20, 2008 8:10 pm

### hortest path from s to t with which includes all subset

In graphs (V,E) with negative edge weights but with no negative cycles , X <V and s, t in V .
I need an algorithm to decide if exist in the graph shortest path from s to t with
which includes all the nodes from X
i've tried to modify A* , Bellman-Ford algorithms but without success .

maxdiver
Learning poster
Posts: 51
Joined: Tue Sep 04, 2007 2:12 pm
Location: Russia, Saratov
Contact:

### Re: hortest path from s to t with which includes all subset

I don't think it's a polynomial-solvable problem.
I suggest an O (M 2^K (logN + K)) algorithm (N - number of vertices, M - ribs, K - number of selected vertices). Let's make another graph, with N 2^K vertices, i.e. each vertex is a pair (original_vertex, visited_mask), what means that we stand in a original graph at original_vertex and we've visited some of the selected vertices according to a visited_mask. We should build ribs in the new graph. After that running dijkstra on this graph from vertex (start_vertex, 0) to find a shortest path to (end_vertex, (2^K)-1).

nicoletsg
New poster
Posts: 15
Joined: Sat Dec 20, 2008 8:10 pm

### Re: hortest path from s to t with which includes all subset

Hi
many thanks for your help. but i'm trying to understand the technique u described.
for the moment for me looks ofuscated . hwy 2^K factor.

I think that we may have k! masks (all permutation of the k nodes.)

I was thinking to something like
calculate the distance between the two subraphs :
(start_node) (must pass nodes)
(must pass_nodes) end_node
and kind of MST in the subgraph wih k nodes
will this work ?
and how is the best way to calculate the distance between start and subgraph K
min {(s-> k_i) i in K}

corbu
New poster
Posts: 10
Joined: Wed Jan 07, 2009 1:57 am

### Re: hortest path from s to t with which includes all subset

for the case |K| =1. there is an intersting discusion on topcoder:
http://forums.topcoder.com/?module=Thre ... rt=0&mc=24
but i not see how can be for the general case.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: hortest path from s to t with which includes all subset

corbu wrote:for the case |K| =1. there is an intersting discusion on topcoder:
http://forums.topcoder.com/?module=Thre ... rt=0&mc=24
but i not see how can be for the general case.
That thread describes a different version of this problem, in which we're looking for shortest simple path (i.e. repeated vertices are forbidden).
nicoletsg wrote:Hi
many thanks for your help. but i'm trying to understand the technique u described.
for the moment for me looks ofuscated . hwy 2^K factor.
You construct a new graph H = (V', E'), where V' is a set of pairs (u, S), such that u is a vertex from V, and S is a subset of X. If set X has size K, then it has 2^K subsets, that's where 2^K factor comes from.
I think that we may have k! masks (all permutation of the k nodes.)
...
I'm not sure I understand what you're trying to say.
But if enumerating all k! permutations of elements of X is acceptable to you, then you can simply compute value dist(s, x1) + dist(x1, x2) + ... + dist(x_k, t) for each such permutation x1,x2,...,x_k, and choose the cheapest of them, which will be the answer. (dist(x, y) here is length of shortest path between x and y - use Floyd-Warshall algorithm to precompute these values.)

corbu
New poster
Posts: 10
Joined: Wed Jan 07, 2009 1:57 am

### Re: hortest path from s to t with which includes all subset

maxdiver wrote:I don't think it's a polynomial-solvable problem.
I suggest an O (M 2^K (logN + K)) algorithm (N - number of vertices, M - ribs, K - number of selected vertices). Let's make another graph, with N 2^K vertices, i.e. each vertex is a pair (original_vertex, visited_mask), what means that we stand in a original graph at original_vertex and we've visited some of the selected vertices according to a visited_mask. We should build ribs in the new graph. After that running dijkstra on this graph from vertex (start_vertex, 0) to find a shortest path to (end_vertex, (2^K)-1).
HI maxdiver,
Please can u explain abit this ? there is any refences (book paper desribing graph super construction)I never met this idea
how this graph would be for 1 or 2 nodes?
thanks a lot

maxdiver
Learning poster
Posts: 51
Joined: Tue Sep 04, 2007 2:12 pm
Location: Russia, Saratov
Contact:

### Re: hortest path from s to t with which includes all subset

Ok.
Let's have a graph
1 -> 2, 2 -> 3, 3 -> 4, 1 -> 3, 2 -> 4
and the only marked vertex is 2.
So the problem is to find a path from 1 to 4 , visiting vertex 2.

Let's build new graph G' (a 'state graph'), in which each vertex is a pair (v,m), here m can take only two values: 0 or 1 (mask of length 1, because here we have only one selected vertex).
Build ribs in this graph:
(1,0) -> (2,1) (if we were in vertex 1 and haven't visited selected vertex before, than after going to 2 we mark in the mask that we've visited it)
(1,1) -> (2,1) (nothing changes)
(2,1) -> (3,1) (we've visited vertex 2, that is marked in mask, so this remains in mask)
(3,0) -> (4,0) (before going to 4 from 3 we haven't visited selected vertex, and after going to 4 neither)
(1,0) -> (3,0)
(1,1) -> (3,1)
(2,1) -> (4,1)
and from vertex (2,0) there are no ribs, this is an absolutely unfeasible state.

If there were two selected vertices, than each mask would take values from 0..3, where first bit of the mask saves information about have we visited first selected vertex or not; similarly, the second bit.

P.S. So long post, a big test of my English corbu
New poster
Posts: 10
Joined: Wed Jan 07, 2009 1:57 am

### Re: hortest path from s to t with which includes all subset

maxdiver wrote:Ok.
Let's have a graph
1 -> 2, 2 -> 3, 3 -> 4, 1 -> 3, 2 -> 4
and the only marked vertex is 2.
So the problem is to find a path from 1 to 4 , visiting vertex 2.
Let's build new graph G' (a 'state graph'), in which each vertex is a pair (v,m), here m can take only two values: 0 or 1 (mask of length 1, because here we have only one selected vertex).
Build ribs in this graph:
(1,0) -> (2,1) (if we were in vertex 1 and haven't visited selected vertex before, than after going to 2 we mark in the mask that we've visited it)

P.S. So long post, a big test of my English thanks for explanations,math is international. what are the wights for the new graph ?
well very nice imagination you have.

maxdiver
Learning poster
Posts: 51
Joined: Tue Sep 04, 2007 2:12 pm
Location: Russia, Saratov
Contact:

### Re: hortest path from s to t with which includes all subset

thanks for explanations,math is international. what are the wights for the new graph ?
Weights stay the same. That is, if there is any rib a -> b, than in new graph each rib (a,x) -> (b,y) (of course, if the rib exists) will have the same weight.
well very nice imagination you have.
This idea is not something outstanding, quite a usual application of bit masks.

corbu
New poster
Posts: 10
Joined: Wed Jan 07, 2009 1:57 am

### Re: hortest path from s to t with which includes all subset

do u see any easier easy solution if the K =V.
That means to find a shortest path if the graph must pass through all the nodes of a complete graph .
a kind of shortest hamiltonian path ?

I asked this because the problem can be reduced to a hamiltonian path if
we construct a graph complete G1= (V1, E1) V1 =K U {s,t}
w(x1,x2) = length of shortest path from x1 to x2 in G(V,E)
Last edited by corbu on Wed Jan 21, 2009 12:39 am, edited 1 time in total.

corbu
New poster
Posts: 10
Joined: Wed Jan 07, 2009 1:57 am

### Re: hortest path from s to t with which includes all subset

maxdiver wrote:
thanks for explanations,math is international. what are the wights for the new graph ?
Weights stay the same. That is, if there is any rib a -> b, than in new graph each rib (a,x) -> (b,y) (of course, if the rib exists) will have the same weight.
well very nice imagination you have.
This idea is not something outstanding, quite a usual application of bit masks.

there is anywhere tis into a paper , course book or code ?

maxdiver
Learning poster
Posts: 51
Joined: Tue Sep 04, 2007 2:12 pm
Location: Russia, Saratov
Contact:

### Re: hortest path from s to t with which includes all subset

do u see any easier easy solution if the K =V.
That means to find a shortest path if the graph must pass through all the nodes of a complete graph .
a kind of shortest hamiltonian path ?

I asked this because the problem can be reduced to a hamiltonian path if
we construct a graph complete G1= (V1, E1) V1 =K U {s,t}
w(x1,x2) = length of shortest path from x1 to x2 in G(V,E)
Yes, in this case your problem is exactly a hamiltonian-path problem, which is NP-complete, so there is no polinomial algorithm for the problem.
Solution with masks, which I described here, is non-polinomial, quite slow. Btw, hamiltonian-path problems are often solved with binary masks.
there is anywhere tis into a paper , course book or code ?
I don't know, I think it should be described somewhere. This method is a kind of dynamical programming (on binary masks), try searching with this. Try searching for a solution of hamiltonian-path problems based on the idea with masks - it is a very popular problem, and it's definitely described somewhere.