c - バイナリ行列の 2 点間の最短経路

Question

バイナリ行列の 2 点間の最短経路を見つけたいです。

マトリックスのソースと宛先はユーザーが指定します。行列の 1 の位置のみを選択でき、斜め、左、右、上下にも移動できます。

移動が対角線の場合、コストはルート 2 です。それ以外の場合は 1 です。したがって、それを見つける方法のアルゴリズムが必要です。

Answer 1

探しているのは、単一ソースの最短パス アルゴリズムです。つまり、グラフ内のソース ノードを選択し (たとえば)、すべてまたは 1 つのノードへの最短パスを見つけます。この目的のためにいくつかのアルゴリズムが存在します -

• ダイクストラのアルゴリズム

• ベルマンフォードアルゴリズム

• スターサーチアルゴリズム

• フロイド・ウォーシャル・アルゴリズム

• ジョンソンのアルゴリズム

これらを読んで、目的に適したものを選択することをお勧めします。