## Search found 10 matches

Wed Jan 21, 2009 12:05 am
Forum: Algorithms
Topic: hortest path from s to t with which includes all subset
Replies: 11
Views: 2369

### 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 no...
Wed Jan 21, 2009 12:02 am
Forum: Algorithms
Topic: hortest path from s to t with which includes all subset
Replies: 11
Views: 2369

### 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, E...
Tue Jan 20, 2009 1:51 pm
Forum: Algorithms
Topic: hortest path from s to t with which includes all subset
Replies: 11
Views: 2369

### 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 ...
Wed Jan 14, 2009 1:55 pm
Forum: Algorithms
Topic: hortest path from s to t with which includes all subset
Replies: 11
Views: 2369

### 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...
Wed Jan 14, 2009 1:33 am
Forum: Algorithms
Topic: hortest path from s to t with which includes all subset
Replies: 11
Views: 2369

### 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.
Mon Jan 12, 2009 6:03 pm
Forum: Algorithms
Topic: shortest track
Replies: 4
Views: 1125

### Re: shortest track

thank you so much for the time you took to look into the term of the problem and to draw the solution. sorry for my bad translation . It thought that arcs , tracks are part of the math heritage. it seems that is not. after i consulted with other big brains and i read more carefully the problem it re...
Wed Jan 07, 2009 11:33 pm
Forum: Algorithms
Topic: shortest track
Replies: 4
Views: 1125

### Re: shortest track

the corect text is i have a problem and i have no idea of how to start. there is a graph direct with weights that are real and a set of arcs F. A track is named "strained " related to F if any arc (uv) from track is either in F or there is no outgoing arc from u in set F. given 2 vertexes source and...
Wed Jan 07, 2009 9:31 pm
Forum: Algorithms
Topic: shortest track
Replies: 4
Views: 1125

### shortest track

hi all i have a problem and i have no idea of how to start. there is a graph direct with weight in R and a set of lines S. a track is considered "strained " related with S if any line (uv) are either in S or there is no outgoing line from u in set s . ( the algorithm should answer if there exist a s...
Wed Jan 07, 2009 9:18 pm
Forum: Algorithms
Topic: edge in all the shortest paths
Replies: 3
Views: 1069

### Re: edge in all the shortest paths

i'm thinking if we can find if there is at least one path going through a line.
my approach is to memorate all shortest path (if i use dijkstra ) in a arrays of paths
and check if the magic line is in the array.
u think it would work with negative edge ?

does anyone have other idea ?
thanks
Wed Jan 07, 2009 9:10 pm
Forum: Algorithms
Topic: order products efficient
Replies: 3
Views: 956

### Re: order products efficient

not sure if is right. intuitively is like this. but think at a graph (complete)
and the MST . then we just have the choose the adiacente number in the sorted array but win min values.
are these equivalente ? same solution?