I need to construct a graph with the following properties:
- $w(u, v)$ = $-w(v, u)$, for every edge $(u, v) \in E$
- Weight of all $u \leadsto v$ paths is equal, for every $u, v \in V$ (this is zero weight cycle property from the title).
- Weight of $s \leadsto t$ paths is maximal, for some input vertices $s$ and $t$
Yes, this originates from a flow problem.
And I know an algorithm that performs such construction. Let $d(u)$ denote $|s \leadsto u|$, the length of every path from $s$ to $u$.
Initialization:
Let $d(s) \leftarrow 0$, $d(t) \leftarrow 1$ and $d(v) \leftarrow$ some real value from $[0, 1)$, for every other vertex.
Advance:
ITERATIONS ← some big value
perform ITERATIONs times:
new_d ← array for zeros
for ( vertex v in V ) # visit order is arbitrary
sum ← 0
for ( every edge (v, u) )
sum ← sum + d[u]
d[v] ← sum / degree[v] # d[v] is an Arithmetic mean.
d ← new_d
d[s] ← 0
d[t] ← 1
end
That's it. Weight of edge $(u, v)$ is equal to $d(u) - d(v)$. I mentioned maximization of $s \leadsto t$ paths, and they are indeed maximal, as $d(v) < 1$ for every $v \neq t$. Weight can now scaled.
An example of algorithm output:
$0.384 = \frac{(0.461 + 0.539 + 0.154)}{3}$ and $0.154 = \frac{(0 + 0 + 2.30 + 3.84)}{4}$ I didn't draw inverse edges for convenience.
I don't know why this algorithm works as I don't get why arithmetic mean should be picked. Could anyone explain the sequence of thought one could get to arrive at the idea that distance to vertex should be an arithmetic mean of neighbour distances for the graph to satisfy second property?
