$x_i,x_j$ 間の最短経路と $x_k,x_l$ 間の最短経路で同じ辺を用いている場合、その辺に対応する操作は行わなくてよいため、正確なコストの計算は難しいです。ここで、最適解において、 $x_i,x_j$ 間の最短経路と $x_k,x_l$ 間の最短経路には同じ辺がないようなものがあることを示します。これにより、そのようなペア分けをした場合の操作のコストは簡単に求まります。

\(x_i\) から \(x_j\) までの最短経路で使った辺を \(x_i\) に近い順に \(e_1,e_2, \cdots , e_a\) とします。 \(x_k,x_l\) に対しても同様に考えて、 \(e'_1,e'_2, \cdots e'_b\) とします。ここで、 \(e_p = e'_q\) とします。
ここで、 \(x_i\) と \(x_k\) 間の経路は \(e_1,e_2, \cdots , e_{p-1} , e'_{q-1} , e'_{q-2} , \cdots , e'_1\) がありえ、 \(x_j\) と \(x_l\) 間の経路は \(e_a,e_{a-1}, \cdots , e_{p+1} , e'_{q+1} , e'_{q+2} , \cdots , e'_b\) がありえます。この時、経路の長さの合計は最初のものよりも小さいことに着目すると、最初のペア分けは最適でないことが分かります。