Lazy updateを用いた最短経路高速近似解法

摘要

本稿は，最短経路問題を解くダイクストラアルゴリズムに対する高速近似解法を提案する．従来のダイクストラアルゴリズムでは，距離が未確定の頂点のうち，最小仮距離の頂点を1点選択し，その頂点の隣接頂点の仮距離を更新する．この手法は，選択頂点の仮距離がこれ以上更新しないことを利用して最適性を保証しているが，この距離更新がされない頂点が一個とは限らない．そこで，本稿では，これらの頂点を全て選択し，まとめて距離確定とするLazy update手法を利用することで計算時間の削減を実現した．また，誤差を許容すれば，更に高速になることもわかった．そして，実験により，ある程度の誤差を許容すれば，10倍程度の高速化が確認できた．