<p>I have a graph-problem which seems to be not very exotic but I do not know its proper name.</p>

<p>As given in the heading I am looking for a path between two given vertices that maximises the product of weights along the path, were all weights are in [0,1].</p>

<p>Coverstory is that vertices are states and weights denote the probability of a transition along that edge. Since the probabilities are independent, the product is the probability that this path will happen.</p>

<p>Any help with this would be appreciated especially the name of the problem or related google keywords, possible transformations into well known problems and/or an intuition about its complexity.</p>

<p>Thanks!</p>

CC BY-SA 3.0
2012-08-07T10:05:28.407Z
(hoping this is not homework) Try to take $\log$'s of the weights.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2012-08-07T12:04:50.950Z
Not it is not homework. Realising that it is somewhat trivial, I understand where that suspection comes from.
In fact I should take log(1-w) and make it a shortest path problem. Minimising the probability that a given path does not happen.
Many thanks.
Alex
CC BY-SA 3.0
2012-08-07T15:02:32.720Z
The question doesn't seem research-level (as explain in our [FAQ]), would you like us to migrate the question to [cs.se] where it can be suitable?
Kaveh
CC BY-SA 3.0
2012-08-07T18:53:01.953Z
Voting to close (or migrate); this is not a research-level question.  I have used this exact question in undergraduate algorithms exams.
Jeffε
<ds.algorithms><graph-theory>
Finding a path between two given vertices that maximises the product of weights
Alex
# Finding a path between two given vertices that maximises the product of weights

(Asked by: username_0 on 2012-08-07)

I have a graph-problem which seems to be not very exotic but I do not know its proper name.

As given in the heading I am looking for a path between two given vertices that maximises the product of weights along the path, were all weights are in [0,1].

Coverstory is that vertices are states and weights denote the probability of a transition along that edge. Since the probabilities are independent, the product is the probability that this path will happen.

Any help with this would be appreciated especially the name of the problem or related google keywords, possible transformations into well known problems and/or an intuition about its complexity.

Thanks!

**Tags:** ds.algorithms, graph-theory
> **Comments:**
> **username_1**: (hoping this is not homework) Try to take $\log$'s of the weights.  
> **username_0**: Not it is not homework. Realising that it is somewhat trivial, I understand where that suspection comes from. In fact I should take log(1-w) and make it a shortest path problem. Minimising the probability that a given path does not happen. Many thanks.  
> **username_2**: The question doesn't seem research-level (as explain in our [FAQ]), would you like us to migrate the question to [cs.se] where it can be suitable?  
> **username_3**: Voting to close (or migrate); this is not a research-level question.  I have used this exact question in undergraduate algorithms exams.  

---

## 0 answers

