shortest-path - 最短経路の検索

Question

グラフに点のセットがあります。水平、垂直、または左右 45 度の線を使用して、このグラフのサブセットを結ぶ最短経路を見つけたいと考えています。これを行うためのアルゴリズムを提案できる人はいますか?

Answer 1

直線的な最小ステニア木の問題の解決策を修正する必要があると思います。