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.


  • 3
    $\begingroup$ (hoping this is not homework) Try to take $\log$'s of the weights. $\endgroup$ – Kristoffer Arnsfelt Hansen Aug 7 '12 at 10:05
  • $\begingroup$ 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. $\endgroup$ – Alex Kornrumpf Aug 7 '12 at 12:04
  • $\begingroup$ The question doesn't seem research-level (as explain in our FAQ), would you like us to migrate the question to Computer Science where it can be suitable? $\endgroup$ – Kaveh Aug 7 '12 at 15:02
  • 3
    $\begingroup$ Voting to close (or migrate); this is not a research-level question. I have used this exact question in undergraduate algorithms exams. $\endgroup$ – Jeffε Aug 7 '12 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.