グラフ - ダイクストラのアルゴリズム - タイルベースのマップ - グラフに「ブロッキング」という用語がありますか？

Question

タイルベースのマップがあるとします。各タイル（頂点）は、8つの隣接タイルまでのエッジを有する。これらのタイルの1つに壁があります（これは完全にブロックしています）。

数学的な観点から、それは（壁がされている）その頂点を意味するのでしょ：

1. は存在しませんか？
2. この頂点にエッジはありませんか？
3. 頂点はちょうどブロックしています - この用語はグラフのteoryにありますか？

Answer 1

理論的には、これは通常、（1）ノードが存在しないとしてモデル化されます。しかし、Dijkstraのアルゴリズムの実装では、通常、アルゴリズムを使用してグラフを横断するために隣接ノードのシーケンスにノードをマップする関数があります。その機能は、（1）ノードが存在しないか、（2）エッジが「ブロッキング」ノードに入射していないと解釈される可能性のある「ブロッキング」ネイバーを単純に戻さない。どのようにそれを解釈することを選択するかは重要ではありません—実装は同じになります。