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

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

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?

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?