I have a problem where I have a directed acyclic graph that represents routes across cities and each edge $(u,v)$ has a weight value $ w(u,v) $ between 0-1 that represents the probability of success crossing the route.
I have to use Dijkstra to navigate the graph and find the most trusty path from vertex $ s $ to vertex $ t $. So, get a higher probability possible.
The problem is, Dijkstra navigates getting the minimum sum of the weight across the path between $ s $ and $ t $.
what I got: I got the inverted values (so now each edge represents the untrusty $ (1 - trusty) $ and running Dijkstra on this new graph I will get the minimum sum.
So, the $ k $ vertex that belongs to this path $ (v_0, v_1, v_2,..., v_k) $ are the lowest values on this path of "untrusty". Consequently, it is the highest values talking about "trusty".
So, will this $ k $ vertex give me a higher probability?
Like, getting all the story aside, is the same numbers the minimize a sum, minimize a product?
(i know from a fact, from my teacher that the answer is false but the intuition says its true, but i cant figure it out.
No. Minimizing/maximizing the sum is not the same as minimizing/maximizing the product. $1+100 > 10+11$ but $1\cdot 100 < 10\cdot 11$
However, minimizing/maximizing the sum of logarithms is the same as minimizing/maximizing the product (of non-negative numbers).