グラフ用の行列にノードを接続する

Question

こんにちは私はチェスボードに似たJavaで行列を構築する必要があるこの小さなプロジェクトに取り組んでいます。私は、ナイトをポイントから別のものに得るようになっています（ナイトの動きの方法で）。だから私は最後にそこに着くための最短方法を見つける必要があります。

私の問題は、私はその点に到達するためにエッジを接続することはできません。私は、頂点が有効な移動であるかどうかを知ることができますが、その点に到達するためのノードを作成する方法を見つけることができないようです。例えば、

0 XXXXX

1 XXXOX

2 XXXXX

3 XXKXX

4 XXXXX

5 XXXXX

Iは、接続ノードを作成する必要があります後で最短距離を見つけるためにKからOへ。 PS。私はそこに着くか、ちょうどいくつかのヒントを得る方法のヒントで大丈夫になるでしょう。実際には正確なコードは必要ありません。どうもありがとうございました！ 行列の悪い表現だとわかっていますが、私に批判を惜しまないでください。

Answer 1

古典Breadth-First-Searchは、おそらく最も簡単な方法です。したがって、宛先へのパスがあれば、それを見つけるでしょう。さらに、パスは順序または長さの昇順で列挙されるため、最初のパスは最短パスになります。

Answer 2

チェスボードは2次元配列で実装できます。行列内の各セルは、グラフ内のノード（または頂点）とみなすことができます。エッジは2つのノード（この場合は2つのセル）で構成され、一方はfromまたはsource [ノードAと呼ぶことができます]と他はtoまたはneighborまたはdestinationノード[ノードBと呼ぶことができます]。

node Aからnode Bに移動する可能性がある場合は、エッジが終了します。

Dijkstra's algorithmを使用できます。 http://krishnalearnings.blogspot.in/2015/07/implementation-in-java-for-dijkstras.html

ナイトの位置を持つノードでは、ナイトがミニヒープに移動して追加できるセルの可能性を確認できます。各エッジの重みは一定です。ノードのコストを更新するだけで済みます。

class Location { 
    int x; 
    int y; 

    List<Location> adjacent() { 
     // TODO return list of locations reachable in a single step 
    } 
} 

List<Location> findShortestPath(Location start, Location destination) { 
    Location[][] previous = new Location[8][8]; 

    Deque<Location> queue = new ArrayDeque<>(); 
    queue.add(start); 
    do { 
     Location loc = queue.poll(); 
     for (Location n : loc.neighbors()) { 
      if (previous[n.x][n.y] == null) { 
       previous[n.x][n.y] = loc; 
       queue.add(n); 

       if (n.x == destination.x && n.y == destination.y) { 
        // we've found a way, let's reconstruct the list of steps 
        List<Location> path = new ArrayList<>(); 
        for (Location l = n; l != start; l = previous[l.x][l.y]) { 
         path.add(l); 
        } 
        path.reverse(); 
        return path; 
       } 
      } 
     } 
    } while (!queue.isEmpty()); 
    return null; // no path exists 
} 

このコードは、開始位置からのすべてのパスを列挙：