Algorithm Theory¶
Problem Statement¶
Given a directed graph \(G=(V,E)\) where each edge \(e\in E\) has a cost \(c_e\) and a time \(t_e\), the goal is to find a cycle \(C\) that minimises the ratio
The optimal value \(r^*\) is the minimum of \(r(C)\) over all directed cycles in the graph.
Lawler’s Parametric Search¶
The solver follows Lawler’s approach by repeatedly asking whether a candidate ratio \(\lambda\) is too high. Each edge weight is shifted according to
If the transformed graph contains a negative cycle, then a feasible solution with ratio less than \(\lambda\) exists; otherwise the optimum is at least as large as \(\lambda\). By binary searching on \(\lambda\) we obtain a ratio within a specified tolerance.
Binary Search Strategy¶
The search maintains lower and upper bounds \(\lambda_{\text{lo}}\) and
\(\lambda_{\text{hi}}\) on the optimal ratio. At each step the midpoint
\(\lambda=(\lambda_{\text{lo}}+\lambda_{\text{hi}})/2\) is tested. If a
negative cycle is found, the optimum lies below and the upper bound is
updated; otherwise the lower bound increases. Iteration continues until
hi - lo is below a user supplied tolerance, ensuring convergence in
\(O(\log((\lambda_{\text{hi}}-\lambda_{\text{lo}})/\text{tol}))\)
iterations.
Worked Example¶
Consider a triangle with edges \(0\to1\to2\to0\) and edge weights \((c,t) = (2,1),(3,2),(1,1)\). Testing \(\lambda=1\) produces shifted weights \(w_1 = (1,1,0)\). The resulting negative cycle indicates the ratio is less than one, so the binary search narrows the interval accordingly.
Stern–Brocot Exact Search¶
When all weights are integers the optimum ratio is rational. The solver can switch to an exact mode that performs a Stern–Brocot search on the tree of positive rationals. The algorithm maintains bounding fractions \(\frac{a}{b} < r^* < \frac{c}{d}\) and refines them using mediants \(\frac{a+c}{b+d}\) until the exact ratio is located, eliminating floating point error.
Vectorised Bellman–Ford¶
Negative cycle queries are answered using a Bellman–Ford relaxation scheme implemented with NumPy arrays. For \(n\) vertices and \(m\) edges the method performs \(O(nm)\) relaxations but operates on whole arrays at a time, yielding significant speedups over a pure Python implementation.
Complexity¶
Combining the binary search with the relaxation phase yields a total running time of \(O(nm \log((\lambda_{\text{hi}}-\lambda_{\text{lo}})/\text{tol}))\). When the exact Stern–Brocot mode is used the search depth is bounded by the size of the optimal numerator and denominator, providing a polynomial guarantee for integer-weighted inputs.