Find shortest path for a volatile graph
Here is a rough sketch of an iteratively improving algorithm that I believe should work pretty well while minimizing the number of queries we do. It can also immediately start finding paths and slowly improve the paths it finds as it goes.

The first step is to evaluate every edge (if you wish to improve initial accuracy, evaluate every edge $k$ times) and use Dijkstra's to find the shortest distance $d_v$ from every vertex $v$ to the target vertex. This forms our initial belief of the graph.

Our goal is to find an accurate $\mu_e$ average weight for each vertex, but we want to be most certain about our precision "near" what we believe to be the optimal path(s). We do this by repeatedly finding a path from the start vertex to the target, in a probabilistic fashion, by repeating the following procedure:

If we are currently at vertex $v$ we have a choice from some edges. We currently believe that each edge has weight $\mu_e$, and when we take that edge we would get to vertex $w$ with remaining (believed) distance $d_w$. We consider this a multi-armed bandit problem, where choosing edge $e$ going to vertex $w$ would have cost $\mu_e + d_w$, and we want to minimize cost. We use this to probabilistically choose an edge, we query its weight, we update $\mu_e$ and $d$ with this new weight and then move to $w$.

As we keep repeating the above process we will balance exploration of the graph with exploitation automatically due to the multi-armed bandit.