# How to prove this equation?

• Ganesh Ujwal

#### Ganesh Ujwal

Member warned about not using the homework template
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.

## 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.

Last edited: