BFS アルゴリズムを使用してグラフを探索し、最短パスを出力します

Question

<p>プログラムの目標は、さまざまな空港を通過し、幅優先検索アルゴリズムを使用して PHX と BKK 間の最短経路を出力することです。 <strong>しかし、結果を印刷するのに問題があります。 </strong></p> <p>予想される出力 (最短パス) は次のとおりです: PHX -> LAX -> MEX -> BKK

<pre class="brush:php;toolbar:false;">const Airport = 'PHX BKK OKC JFK LAX MEX EZE HEL LOS LAP LIM'.split(' '); const ルート = [ ['PHX'、'LAX']、 ['PHX'、'JFK']、 ['JFK'、'OKC']、 ['JFK'、'ヘル']、 ['JFK'、'LOS']、 ['メキシコ'、'ロサンゼルス']、 ['メキシコ'、'BKK']、 ['MEX', 'LIM'], ['MEX'、'EZE']、 ['リム'、'BKK']、 ]; //グラフ const adjacencyList = new Map(); //ノードを追加 関数 addNode(空港) { adjacencyList.set(空港, []); } // エッジを無向に追加します 関数 addEdge(起点, 終点) { adjacencyList.get(origin).push(destination); adjacencyList.get(目的地).push(出発地); } // グラフを作成する Airport.forEach(addNode); // 各ルートをループし、値を addEdge 関数に展開します Routes.forEach(route => addEdge(...route));</pre> <p>ノードを開始点 (サイト)、エッジを目的地として、グラフは無向です。</p> <pre class="brush:php;toolbar:false;">function bfs(start) { const 訪問 = new Set(); Visited.add(start); // 開始ノードを訪問済みリストに追加します const キュー = [開始]; while (キューの長さ > 0) { const Airport = queue.shift(); // キューを変更します const destinations = adjacencyList.get(空港); for (宛先のconst宛先) { if (宛先 === 'BKK') { console.log(`BFS がバンコクを発見しました!`) //コンソール.ログ(パス); } if (!visited.has(目的地)) { 訪問済み.追加(目的地); キュー.プッシュ(宛先); } } } } bfs('PHX')</pre></p>

Answer 1

コメント内の InSync の提案に従って問題を解決できました。

bfs() 関数では、各ノード (親ノード) がたどるパスを保存するために oldpath が使用され、結果を保存するために最短パスが使用されます。 リーリー リーリー

新しい関数の機能は非常に単純です。親ノードを ShortestPath に追加し、親ノードの親ノード (存在する場合) を検索します。現在の親ノードがルート ノードである場合、ループは終了します

リーリー

Answer 2

ノードを訪問済みとしてマークする代わりに、この機会を利用してノードをその親でマークします。マップを使用して次のことができます:

• ノードが訪問されたかどうかを示します
に到達する前のノード (親ノード) を示します。
• キュー内のノードへのアクセス順序を維持する

また、関数内でグローバル変数を参照することを避け、代わりに必要なものすべてを引数として渡すことをお勧めします。

リーリー