6.7.1.1. Computing \(\boldsymbol{\mu^*_f}\)

To compute \(\mu^*_f\), we choose an arbitrary vertex \(s\) as the source and compute distance labels \(\ell^{(0)}_x, \ldots, \ell^{(n)}_x\) for all vertices \(x \in V\). We initialize \(\ell^{(0)}_s = 0\) and \(\ell^{(0)}_x = \infty\) for all \(x \ne s\) as in the Bellman-Ford algorithm. Then we run the algorithm for \(n\) iterations. The \(i\)th iteration computes \(\ell^{(i)}_x\) for all \(x \in V\). In contrast to the Bellman-Ford algorithm, which sets

\[d^{(i)}_y = \min\left(d^{(i-1)}_y, \min_{(x,y) \in E} \left(d^{(i-1)}_x + c^f_{x,y}\right)\right),\tag{6.10}\]

we define

\[\ell^{(i)}_y = \min_{(x,y) \in E} \left(\ell^{(i-1)}_x + c^f_{x,y}\right).\]

Thus, \(\ell^{(i)}_x\) is the length of a shortest walk from \(s\) to \(x\) with exactly \(i\) edges, whereas the distance label \(d^{(i)}_x\) computed by the Bellman-Ford algorithm is the length of a shortest walk from \(s\) to \(x\) with at most \(i\) edges. The vertex labellings \(\ell^{(0)}, \ldots, \ell^{(n)}\) can clearly be computed in \(O(nm)\) time. The following lemma provides the means to compute \(\mu^*_f\) from \(\ell^{(0)}, \ldots, \ell^{(n)}\) in \(O\bigl(n^2\bigr)\) time. Thus, \(\mu^*_f\) can be computed in \(O(nm)\) time in total.

Lemma 6.31:

\[\mu^*_f = \min_{x \in V} \max_{0 \le i \le n - 1} \frac{\ell^{(n)}_x - \ell^{(i)}_x}{n - i}.\tag{6.11}\]

Proof: We consider two cases:

\(\boldsymbol{\mu^*_f = 0}\): Under this assumption, there is no negative-cost cycle in \(G^f\). Thus, every vertex \(x\) has a well-defined distance \(d_x\) from \(s\). Let \(d^{(0)}, \ldots, d^{(n)}\) be the distance labellings the Bellman-Ford algorithm would have produced using the equalities (6.10). Then \(d^{(0)}_x \ge \cdots \ge d^{(n)}_x = d_x\) and \(\ell^{(i)}_x \ge d^{(i)}_x\) for all \(x \in V\) and all \(0 \le i \le n\). In particular, \(\ell^{(i)}_x \ge d_x\) for all \(x \in V\) and all \(0 \le i \le n\).

Claim 6.32: For every vertex \(x \in V\), \(\displaystyle\max_{0 \le i \le n-1}\frac{\ell^{(n)}_x - \ell^{(i)}_x}{n - i} \ge 0\).

Claim 6.33: There exists a vertex \(x \in V\) that satisfies \(\displaystyle\max_{0 \le i \le n-1}\frac{\ell^{(n)}_x - \ell^{(i)}_x}{n - i} \le 0\).

These two claims imply that

\[\min_{x \in V}\max_{0 \le i \le n-1}\frac{\ell^{(n)}_x - \ell^{(i)}_x}{n - i} = 0 = \mu^*_f,\]

that is, the lemma holds in the case when \(\mu^*_f = 0\).

Proof of Claim 6.32: Consider an arbitrary vertex \(x \in V\), let \(P\) be a shortest path from \(s\) to \(x\), and let \(k\) be the number of edges in \(P\). Then \(P\) is a walk from \(s\) to \(x\) with \(k\) edges and of length \(d_x\). Thus, \(\ell^{(k)}_x \le d_x\). Since \(\ell^{(n)}_x \ge d_x\), this implies that \(\ell^{(n)}_x \ge \ell^{(k)}_x\) and thus

\[\max_{0 \le i \le n-1} \frac{\ell^{(n)}_x - \ell^{(i)}_x}{n - i} \ge \frac{\ell^{(n)}_x - \ell^{(k)}_x}{n - k} \ge 0.\ \text{▣}\]

Proof of Claim 6.33: Since \(G^f\) is strongly connected, it contains at least one cycle. Since \(\mu^*_f = 0\), there must exist such a cycle \(C = \langle x_0, \ldots, x_t \rangle\) of cost \(c^f_C = 0\). Let \(P\) be a shortest path from \(s\) to \(x_0\), and let \(k\) be the number of edges in \(P\). By the same argument as in the previous paragraph, \(\ell^{(k)}_{x_0} \le d_{x_0}\). Thus,

\[\ell^{(k+1)}_{x_1} \le \ell^{(k)}_{x_0} + c^f_{x_0,x_1} \le d_{x_0} + c^f_{x_0, x_1}\]

and, inductively,

\[\ell^{(k+h)}_{x_{h \bmod t}} \le d_{x_0} + \sum_{j=1}^h c^f_{x_{j-1}, x_j} \quad \forall 0 \le h \le n - k.\]

For \(h = n - k\) and \(z = x_{(n - k) \bmod t}\), this gives

\[\ell^{(n)}_z \le d_{x_0} + \sum_{j=1}^{n-k} c^f_{x_{j-1}, x_j}.\]

To complete the proof of Claim 6.33, we prove that

\[d_z = d_{x_0} + \sum_{j=1}^{n-k} c^f_{x_{j-1}, x_j}.\tag{6.12}\]

This implies that \(\ell^{(n)}_z \le d_z\).¹ Since \(\ell^{(i)}_z \ge d_z\) for all \(0 \le i \le n\), we thus have

\[\frac{\ell^{(n)}_z - \ell^{(i)}_z}{n - i} \le 0 \quad \forall 0 \le i \le n - 1\]

and, thus,

\[\max_{0 \le i \le n - 1} \frac{\ell^{(n)}_z - \ell^{(i)}_z}{n - i} \le 0.\]

The distance labelling \(d\) satisfies the condition that \(d_y \le d_x + c^f_{x,y}\) for every edge \((x, y) \in G^f\). Thus, if we choose a potential function \(\pi\) defined as \(\pi_x= -d_x\) for every vertex \(x \in V\), then we obtain a reduced cost function \(c^\pi\) that satisfies

\[c^\pi_{x,y} = c^f_{x,y} - \pi_x + \pi_y = c^f_{x,y} + d_x - d_y \ge 0 \quad \forall (x,y) \in G^f.\]

The reduced cost of the cycle \(C\) is

\[c^\pi_C = \sum_{j=1}^t c^\pi_{x_{j-1}, x_j} = \sum_{j=1}^t c^f_{x_{j-1}, x_j} - \sum_{j=0}^{t-1}\pi_{x_j} + \sum_{j=1}^t \pi_{x_j} = c^f_C = 0\]

because \(x_t = x_0\). Since \(c^\pi_{x_{j-1}, x_j} \ge 0\) for all \(1 \le j \le t\), this implies that \(c^\pi_{x_{j-1},x_j} = 0\) for all \(1 \le j \le t\). In other words, \(c^f_{x_{j-1}, x_j} + d_{x_{j-1}} - d_{x_j} = 0\), that is, \(d_{x_j} = d_{x_{j-1}} + c^f_{x_{j-1}, x_j}\). Thus, (6.12) holds. ▣

\(\boldsymbol{\mu^*_f \ne 0}\): In this case, consider edge costs

\[c^r_{x,y} = c^f_{x,y} - \mu^*_f,\]

let \(\mu^*_r\) be the minimum mean cost of any cycle in \(G^f\) with respect to these adjusted edge costs, and let

\[q^{(i)}_x = \ell^{(i)}_x - i\mu^*_f \quad \forall x \in V, 0 \le i \le n.\]

Since \(c^r_{x,y} = c^f_{x,y} - \mu^*_f\), the mean cost of every cycle with respect to \(c^r\) is \(\mu^*_f\) lower than its mean cost with respect to \(c^f\). Thus, \(\mu^*_r = 0\). Moreover, since \(\ell^{(i)}_y = \min_{(x, y) \in E} \Bigl(\ell^{(i-1)}_x + c^f_{x,y}\Bigr)\), we have

\[\begin{aligned} q^{(i)}_y &= \ell^{(i)}_y - i\mu^*_f\\ &= \min_{(x, y) \in E} \left(\ell^{(i-1)}_x + c^f_{x,y} - i\mu^*_f\right)\\ &= \min_{(x, y) \in E} \left(\left(\ell^{(i-1)}_x - (i-1)\mu^*_f\right) + \left(c^f_{x,y} - \mu^*_f\right)\right)\\ &= \min_{(x, y) \in E} \left(q^{(i-1)}_x + c^r_{x,y}\right), \end{aligned}\]

that is, \(q^{(i)}_y\) is the length of a shortest walk from \(s\) to \(y\) with exactly \(i\) edges with respect to the edge costs \(c^r\). Since \(\mu^*_r = 0\), the argument for the case when \(\mu^*_f = 0\) thus shows that

\[\mu^*_r = 0 = \min_{x \in V} \max_{0 \le i \le n - 1} \frac{q^{(n)}_x - q^{(i)}_x}{n - i}.\]

This gives

\[\begin{aligned} 0 &= \min_{x \in V} \max_{0 \le i \le n - 1} \frac{q^{(n)}_x - q^{(i)}_x}{n - i}\\ &= \min_{x \in V} \max_{0 \le i \le n - 1} \frac{\left(\ell^{(n)}_x -n\mu^*_f\right) - \left(\ell^{(i)}_x - i\mu^*_f\right)}{n - i}\\ &= \min_{x \in V} \max_{0 \le i \le n - 1} \left(\frac{\ell^{(n)}_x - \ell^{(i)}_x}{n - i} - \frac{(n-i)\mu^*_f}{n-i}\right)\\ &= \min_{x \in V} \max_{0 \le i \le n - 1} \frac{\ell^{(n)}_x - \ell^{(i)}_x}{n - i} - \mu^*_f, \end{aligned}\]

that is, again,

\[\mu^*_f = \min_{x \in V} \max_{0 \le i \le n - 1} \frac{\ell^{(n)}_x - \ell^{(i)}_x}{n - i}.\ \text{▨}\]