REAL: ALT + Reach

ALT にさらに Reach を加えたものが REAL と呼ぶらしい。

Reach では、各点に到達限界値を保持させて、Landmark などと同様に探索範囲の限定に用いる。到達限界は、各点が最短路に含まれる際に、最も長いパス長である。

そのため非常に多くの最短路問題を繰り返し計算しなければならず、前処理に非常に時間がかかってしまう。そこで、Shortcuts を用いて前処理の高速化を行うようだ。

Shortcuts はその名の通りバイパスとなる枝を追加する事で、これを用いる事で効率よく到達限界値を計算することができる。