Thanks for a great forum. This is my first post here. I am working on a signal processing application and the core of one the main algorithms reduces to a graph theoretical problem.
Let $G=(V,E)$ be a simple connected graph. Each edge is of length 1. In addition, we assign directions to edges. Note that the graph is undirected, as we can traverse each edge in either direction. The assigned direction only determines the weight of each edge (either +1 or -1) depending on the direction of the traverse.
For each pair $v,u \in V$ of vertices, we define anti-distance $d(u,v)=-d(v,u)$, as the weighted average length of all the paths from $u$ to $v$. Note that the weights are dependent on the path and can be negative. The goal is to find $d(u,v)$ for all the pairs.
The algorithm I currently use is to generate many random spanning trees of $G$ (say, using the Aldous-Broder Algorithm), find $d(u,v)$ for each spanning tree (which is unambiguous and easy to find), and then average them all.
For our signal processing application, the input graphs have few hundreds nodes and it takes $\approx 10^5$ spanning trees to get reasonable values. It is practical, but not pretty! The question is whether there is a better way to do this that does not need what is essentially amount to a Monte-Carlo simulation.