# Prove an algorithm. Give directed graph edge weights such that weight of every cycle is 0

I need to construct a graph with the following properties:

1. $w(u, v)$ = $-w(v, u)$, for every edge $(u, v) \in E$
2. Weight of all $u \leadsto v$ paths is equal, for every $u, v \in V$ (this is zero weight cycle property from the title).
3. 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.

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?

• Presumably, a fixed point of this procedure – where every weight is equal to the arithmetic mean of neighbor distances – satisfies the zero weight cycle property. – Yuval Filmus Apr 28 '18 at 11:05