Consider a complete bidirectional weighted graph. Weight of each edge (a,b) is the probability of getting from a to b. So all weights are in range (0,1]. There is a path between `a`

and `b`

if the probability of getting from `a`

to `b`

is greater than a constant `k`

. So we want to choose minimum number of nodes in order to reach all other nodes from these selected nodes. Number of nodes is less than 25.

So I ran a dijkstra from every node in order to find the nodes that are accessible from that node. After that due to the fact n is very small I tried all the combination of choosing nodes to find the minimum answer as desired. But I am getting wrong answer. Note that first I tried dijkstra as the way stated in the problem I mean I multiplied the costs between each successive nodes. After receiving wrong answer I used `-log(weight)`

to specify the weights and ran a classic dijkstra. But still I am getting wrong answer. Any Idea what could be the problem. Could it be double’s error (rounding-off) ?

First Implementation

Second Implementation

Problem Statement