- #1

- 56

- 0

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

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

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.

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.