System of "stochastic equations" Consider a graph with $n$ vertices and $m$ edges. The vertices are labelled with real variables $x_i$, where $x_1=0$ is fixed. Each edge represents a "measurement": for edge $(u,v)$, I obtain a measurement $z \approx x_u - x_v$. More precisely, $z$ is a truly random quantity in $(x_u - x_v) \pm 1$, uniformly distributed and independent of all other measurements (edges).

I am given the graph and the measurements, with the distribution promise for above. I want to "solve" the system and obtain the vector of $x_i$'s. Is there some body of work on problems of this type? 

Actually, I want to solve an even simpler problem: somebody points me to vertices $s$ and $t$, and I have to compute $x_s - x_t$. There are many things to try, like finding a shortest path, or finding as many disjoint paths as possible and averaging them (weighted by the inverse of the square root of the length). Is there an "optimal" answer?

The problem of computing $x_s - x_t$ is itself not completely defined (e.g. should I assume a prior on the variables?)
The area you want to look at for answers to is machine learning. You have desribed a graphical model. I think in this case methods as easy as Belief Propagation should suffice.