Dijkstraの最短経路アルゴリズムの変更

Question

私は個人的なプロジェクトのための画像に取り組んでいます。私はステップで立ち往生しました（さらに、比較的簡単なステップです）。私の質問は途中で画像に関連していません。

イメージの各ピクセルのint値を計算しています。そして、ピクセル間の最小コスト（ノード）のパスを探したいと思います。実際に私はA *アルゴリズムの実装を行っています。しかし、私はそれを使用したくないのです。なぜなら、渡すことができるノードまたは通過できないノードで「マップ」を制限したくないからです。私は、各ノードはコストをかけて渡すことができます。ノードによってはコストがかかるものもあれば、そうでないものもあります。しかし、通過できないノードはありません。

プロジェクトの非常に孤立している部分なので、コードを入力する必要はありません。だから私は誰にも練習したくない。しかし、基本的に私はノードのリストを持つマップオブジェクトを持っています。ノードはid、x、yの位置にあります。 （上、下、左と右のピクセル）と私がここに来た所から知っているノードの参照など。

私はDijkstraの最短経路アルゴリズムとの違いを表現できたらいいと思う。それに応じてどうすれば修正できますか？それとも誰かがこれを行う別の方法をお勧めしますか？

Answer 1

私はこの問題を知っていると思う。「いくつかのノードは非常にコストがかかっていて、いくらかはそうしない」アルゴリズムの実際の動作ではありません。問題をノード（コストなし）とエッジ（コスト付き）に変換する必要があります。それから、A *、Dijkstraまたは他のパス検索アルゴリズムを使用するのは簡単です。

あなたの場合、すべてのピクセルはノード/頂点です。すべてのピクセルには4つのエッジがあります（境界にあるものを除く）。エッジのコストは、宛先ピクセルのint値になります。

また、ノードにノード参照を保持しないでください。ノードの参照先は、アルゴリズムのジョブで、どこから来たのかを記録しておく必要があります。

これが役に立ちます。