ダイクストラ?

A*(A Star)なら、コストに直線距離を指定すれば、
直線距離で近いものから探索していくから、
速く答えを見つけるので、無駄な探索をしなくてすむ