Proving the Minimum Directed Cycle Mean Cost Using Bellman-Ford Algorithm

[Ganesh Ujwal]

Prove $\displaystyle \lambda=\min_{i = 1,\ldots, n}\max_{0 \le k \le n-1}\left(\frac {p_i(n)-p_i(k)}{n-k}\right)$
Prove the minimum directed cycle mean cost satisfies: $\lambda = \min_{i = 1,\ldots, n} \max_{0 \le k \le n-1} \left(\frac {p_i(n) - p_i(k)} {n-k}\right)$ using the Bellman-Ford algorithm.Let $\mathcal G = (\mathcal V, \mathcal A)$ be directed graph with associated edge costs $c_{i,j}$ that has at least one directed cycle ($c_{i,j} = \infty$ for all $(i,j) \notin \mathcal A$).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} \left(\frac {p_i(n) - p_i(k)} {n-k}\right)$, 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.

 

[Ganesh Ujwal]

Homework Statement

Prove $\lambda=\min_{i = 1,\ldots, n}\max_{0 \le k \le n-1}\left(\frac {p_i(n)-p_i(k)}{n-k}\right)$

Homework Equations

This is the part I can't figure out

The Attempt at a Solution

Prove the minimum directed cycle mean cost satisfies:
$\lambda = \min_{i = 1,\ldots, n} \max_{0 \le k \le n-1} \left(\frac {p_i(n) - p_i(k)} {n-k}\right)$using the Bellman-Ford algorithm.

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

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} \left(\frac {p_i(n) - p_i(k)} {n-k}\right)$, 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.