# Find shortest path for a volatile graph

Let me define a volatile graph first:

It is an undirected graph in which the weight of each edge varies every time we query it. That is, when we request the weight w(e) of edge e, we obtain an approximate value ˆw(e) defined as follows: wˆ(e) = w(e) + η, where η ∼ N (0, σ). Here, N (0, σ) is a Gaussian distribution with mean zero and standard deviation σ.

How to obtain a shortest path for such a graph. Let it be denoted as (G, u, v, p). Find the correct shortest path between vertices u and v on a volatile graph G with confidence p. We can define p in any manner we want as long as it is consistent to the fact that as p grows, the probability that our algorithm returns the true shortest path should also grow

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$$.