# Prove a characterisation of the minimum directed cycle mean cost

Let $\mathcal G = (\mathcal V, \mathcal A)$ be directed graph with associated edge costs $c_{i,j}$ that has at least one directed cycle.

Define the directed cycle mean cost to be $\frac {\{\text {sum of cost of arcs}\}} { \text {# arcs}}$.

Set $p_i(0) = 0$ and $p_i(t+1) = \min_{j \in O(i)} \{ c_{i,j} + p_j(t) \}$ for all $i\in \mathcal V$.

I've proven by induction that $p_i(t)$ denotes the length of the shortest walk start starts at $i$ and traverses $t$ arcs.

Now, I want to prove that the minimum directed cycle mean cost $\lambda$ satisfies:

$$\lambda = \min_{i = 1,\ldots, n} \max_{0 \le k \le n-1} (\frac {p_i(n) - p_i(k)} {n-k})$$, where $n$ is the number of vertices in the graph $\mathcal G$.

I see that traversing $n$ arcs will always create a directed cycle. However, I don't know how to continue from here.

• Friendly advice: work on your sheets together with peers. That makes for a much more interactive and productive experience than asking folks on the internet. – Raphael Dec 4 '14 at 14:17
• I dont have any. – Shuzheng Dec 4 '14 at 14:30