Asking smart math people for help!

[wasab]

 

Can smart math people help me out with this question? I am very confused about the highest probability path. What does that mean? 

 

Also, can anyone give me some hints on what O(|V|+|E|) algorithms to use? A tweaked BFS? A tweaked DFS? A modified version of the greedy dijkstra algorithm or something else?

 

@Dash Lambda

Almighty math master Dash Lambda, Can you explain this to me? I am quite stuck :(   

 

 

[Dash Lambda]

The probability of an edge is how likely you are to take that edge, and the probability of a path is how likely you are to take that path. So if your path consists of two edges, one with a probability of .25 and one with a probability of .1, then your path has a probability of (.25)(.1)=.025. If you cross 3 edges with probabilities .3, .2, and .1, the path has probability (.3)(.2)(.1)=.006. You're trying to maximize the probability of the path, the same as finding the maximal path but instead of using a sum you're using a product.

 

Since this looks like a practice/homework problem, I'd rather not give an answer right away. I will say, though, that them choosing a directed acyclic graph is important, because that gives you a way to turn it into a shortest-path problem.

[wasab]

51 minutes ago, Dash Lambda said:

The probability of an edge is how likely you are to take that edge, and the probability of a path is how likely you are to take that path. So if your path consists of two edges, one with a probability of .25 and one with a probability of .1, then your path has a probability of (.25)(.1)=.025. If you cross 3 edges with probabilities .3, .2, and .1, the path has probability (.3)(.2)(.1)=.006. You're trying to maximize the probability of the path, the same as finding the maximal path but instead of using a sum you're using a product.

 

Since this looks like a practice/homework problem, I'd rather not give an answer right away. I will say, though, that them choosing a directed acyclic graph is important, because that gives you a way to turn it into a shortest-path problem.

I see, but I won't be able to use dajiskas alogrithm because it is now finding the max... Unless I invert all the edge weight and make them all negatives? Would that work? If it is DAG, then Dajiskas should work if I flip all the edge weight to negatives right? 

[Dash Lambda]

35 minutes ago, wasab said:

I see, but I won't be able to use dajiskas alogrithm because it is now finding the max... Unless I invert all the edge weight and make them all negatives? Would that work? If it is DAG, then Dajiskas should work if I flip all the edge weight to negatives right? 

You do flip the edge weights, but not by negating them. You negate them when you're adding, but here you're multiplying.

[wasab]

46 minutes ago, Dash Lambda said:

You do flip the edge weights, but not by negating them. You negate them when you're adding, but here you're multiplying.

Oh, forgot about that. Product of two negative makes positive so I can't flip to negatives. 

 

You mean I have to flip the edges differently?  I'm not quite sure how that works.....

[Dash Lambda]

6 minutes ago, wasab said:

Oh, forgot about that. Product of two negative makes positive so I can't flip to negatives. 

 

You mean I have to flip the edges differently?  I'm not quite sure how that works.....

If you're adding up a bunch of positive numbers, the total gets bigger. If you're adding up a bunch of negative numbers, the total gets smaller. So you can flip the sign of the weights to turn a longest-path problem into a shortest-path problem and vise versa.

 

If you're multiplying a bunch of numbers <1, the product gets smaller. If you're multiplying a bunch of numbers >1, the product gets bigger. You can do the same there.

[wasab]

1 hour ago, Dash Lambda said:

If you're adding up a bunch of positive numbers, the total gets bigger. If you're adding up a bunch of negative numbers, the total gets smaller. So you can flip the sign of the weights to turn a longest-path problem into a shortest-path problem and vise versa.

 

If you're multiplying a bunch of numbers <1, the product gets smaller. If you're multiplying a bunch of numbers >1, the product gets bigger. You can do the same there.

Oh! oh! oh! I think I see what you are talking about. So I can flip all edges like this: 1/original weight. 

 The smallest weight will then become the largest and so when multiplying, they will becomes the greatest. Conversly largest becomes the smallest so dajiskas will work and find the smallest but actually is finding the largest. Is my logic correct?

 

Edit: dijkstra I mean. Damn it, I can't spell lol. 

[Dash Lambda]

54 minutes ago, wasab said:

Oh! oh! oh! I think I see what you are talking about. So I can flip all edges like this: 1/original weight. 

 The smallest weight will then become the largest and so when multiplying, they will becomes the greatest. Conversly largest becomes the smallest so dajiskas will work and find the smallest but actually is finding the largest. Is my logic correct?

 

Edit: dijkstra I mean. Damn it, I can't spell lol. 

Yep! You're on the right track.