If all shortest paths are monotonically increasing, we can sort all edges and relax it in increasing order. If all shortest paths are increasing then decreasing, we can sort all edges and relax it in increasing order then relax it in decreasing order.
Extending this idea, the bitonic shortest paths have two situations, one is increasing – decreasing – increasing, another is decreasing – increasing – decreasing. We can sort all edges first, then according two different case relax three times. After combing these two possible solutions, we can get the optimal solution. The time complexity is O(|E| lg |E|).
– 
≥0.
and 
because the shortest path property.
will decrease kt.
, the shortest path is smaller than |E|. We can use the result of a.
≥ 0.
then substitute u by s.![R[i_1, i_2] \times R[i_2,i_3] \times \dots \times R[i_k,i_1] > 1](http://l.wordpress.com/latex.php?latex=R%5Bi_1%2C+i_2%5D+%5Ctimes+R%5Bi_2%2Ci_3%5D+%5Ctimes+%5Cdots+%5Ctimes+R%5Bi_k%2Ci_1%5D+%3E+1&bg=ffffff&fg=000000&s=0 "R[i_1, i_2] \times R[i_2,i_3] \times \dots \times R[i_k,i_1] > 1")
, then ![R[i_1, i_2]^{-1} \times R[i_2,i_3]^{-1} \times \dots \times R[i_k,i_1]^{-1} < 1](http://l.wordpress.com/latex.php?latex=R%5Bi_1%2C+i_2%5D%5E%7B-1%7D+%5Ctimes+R%5Bi_2%2Ci_3%5D%5E%7B-1%7D+%5Ctimes+%5Cdots+%5Ctimes+R%5Bi_k%2Ci_1%5D%5E%7B-1%7D+%3C+1&bg=ffffff&fg=000000&s=0 "R[i_1, i_2]^{-1} \times R[i_2,i_3]^{-1} \times \dots \times R[i_k,i_1]^{-1} < 1")
, then ![\lg R[i_1, i_2]^{-1} + \lg R[i_2,i_3]^{-1} + \dots + R[i_k,i_1]^{-1} < 0](http://l.wordpress.com/latex.php?latex=%5Clg+R%5Bi_1%2C+i_2%5D%5E%7B-1%7D+%2B+%5Clg+R%5Bi_2%2Ci_3%5D%5E%7B-1%7D+%2B+%5Cdots+%2B+R%5Bi_k%2Ci_1%5D%5E%7B-1%7D+%3C+0&bg=ffffff&fg=000000&s=0 "\lg R[i_1, i_2]^{-1} + \lg R[i_2,i_3]^{-1} + \dots + R[i_k,i_1]^{-1} < 0")
. We can set the edge weight with lg R[i,j], and find the negative cycle.
are from small index to high index, it is impossible to create a cycle.
contains whole P, we only need to run one pass then we can get the optimal solution. If there are two consecutive edges which are in different part, then it requires a half pass in the new direction of the path to get the optimal solution. Since the k is at most |V| – 1, the change in direction is not greater than |V| – 2. We can conclude that we need only to run |V|/2 passes.