hortest path from s to t with which includes all subset
Moderator: Board moderators
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* , BellmanFord algorithms but without success .
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* , BellmanFord algorithms but without success .

 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 polynomialsolvable 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).
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
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}
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
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.
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
That thread describes a different version of this problem, in which we're looking for shortest simple path (i.e. repeated vertices are forbidden).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.
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.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.
I'm not sure I understand what you're trying to say.I think that we may have k! masks (all permutation of the k nodes.)
...
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 FloydWarshall algorithm to precompute these values.)
Re: hortest path from s to t with which includes all subset
HI maxdiver,maxdiver wrote:I don't think it's a polynomialsolvable 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).
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

 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
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
thanks for explanations,math is international. what are the wights for the new graph ?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
well very nice imagination you have.

 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
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.thanks for explanations,math is international. what are the wights for the new graph ?
This idea is not something outstanding, quite a usual application of bit masks.well very nice imagination you have.
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)
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.
Re: hortest path from s to t with which includes all subset
maxdiver wrote: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.thanks for explanations,math is international. what are the wights for the new graph ?
This idea is not something outstanding, quite a usual application of bit masks.well very nice imagination you have.
there is anywhere tis into a paper , course book or code ?

 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
Yes, in this case your problem is exactly a hamiltonianpath problem, which is NPcomplete, so there is no polinomial algorithm for the problem.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)
Solution with masks, which I described here, is nonpolinomial, quite slow. Btw, hamiltonianpath problems are often solved with binary masks.
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 hamiltonianpath problems based on the idea with masks  it is a very popular problem, and it's definitely described somewhere.there is anywhere tis into a paper , course book or code ?