How to calculate minimum expected time for searching a graph?

I have a simple graphing problem where I traverse a graph looking for an item. Each node in the graph has a probability n/100 of 开发者_Python百科the item being there, where the sum of all the probabilities equals 1. How can I find the minimum expected time to search for the item in the entire graph?

The item is guaranteed to exist in only one node.

At first glance it seems like a traveling sales person problem and that is simple. Just get the permutations of the the paths and calculate the path for each and return the minimum.

But then it gets tricky when I need to find the minimum expected time. Is there any mathimatical formula that I could plug in on the minimal path to get the result?

ie: sum = 0
    for node in path:
        sum += node.prob * node.weight

Or is there something more complicated that needs to be done?

If all you're doing is looking for a particular item, then you're guaranteed to be at most n lookups.

If the item is 100% guaranteed to exist in the graph, and it will exist exactly once, then you'll find it after approximately n/2 searches. So (time to search one node) * (n / 2) is your expected time.

If you want a better answer than that you need more information.

Also, you should clarify what "each node in the graph has a probability n/100 of the item being there" means. This seems to indicate if I have 1 node in my graph, there's a 1/100 chance of it being on the node I check, but that if I have 100 nodes, I have a 100/100 chance. That, my friend, makes as much sense as a chimpanzee in a tutu.