Page **1** of **1**

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

Posted: **Mon Jan 05, 2009 11:34 pm**

by **nicoletsg**

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 .

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

Posted: **Tue Jan 06, 2009 9:25 pm**

by **maxdiver**

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

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

Posted: **Wed Jan 14, 2009 12:20 am**

by **nicoletsg**

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}

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

Posted: **Wed Jan 14, 2009 1:33 am**

by **corbu**

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.

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

Posted: **Wed Jan 14, 2009 1:50 am**

by **mf**

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

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

Posted: **Wed Jan 14, 2009 1:55 pm**

by **corbu**

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

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

Posted: **Wed Jan 14, 2009 11:28 pm**

by **maxdiver**

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

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

Posted: **Tue Jan 20, 2009 1:51 pm**

by **corbu**

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.

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

Posted: **Tue Jan 20, 2009 3:00 pm**

by **maxdiver**

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.

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

Posted: **Wed Jan 21, 2009 12:02 am**

by **corbu**

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)

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

Posted: **Wed Jan 21, 2009 12:05 am**

by **corbu**

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 ?

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

Posted: **Wed Jan 21, 2009 10:04 am**

by **maxdiver**

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.