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