実は、辞書順最小な移動方法は「ゴールからスタート方向に進めるだけ進む」を繰り返した貪欲な移動の逆再生です。

貪欲でない移動の逆再生は辞書順最小ではないことを、具体例を通して説明します。 例えば（スタートからゴールへの）合法な最短手数の移動 \((a,b,c,d,e)\) において、\(e\) が貪欲でない（つまり \(e<x\) なる \(x\) で、\(x\) 進めるようなものがある）とします。 このとき、最後の 2 項を \( d+e-x, x\) に置き換えた移動\((a,b,c,d+e-x,x)\)は合法であり（最短手数と仮定しているので \(d+e-x > 0\) が成り立ちます）、辞書順で \((a,b,c,d,e)\) よりも早いです。