グラフ内の位置を見つけるために幅優先検索を使用しています。アルゴリズムが正しく機能していると確信していますが、完了したときに結果への最短パスを見つけるのに苦労しています。基本的に、BFS を使用して開始場所から終了場所に到達できますが、端から端までの最短経路を構築する方法がわかりません。どんな助けでも大歓迎です。
ありがとうございました。
質問する
1592 次
1 に答える
5
1つのオプションは次のとおりです。各ノードを「親」ノード (おそらくハッシュ テーブル、または「親」フィールドをノードを表す任意の型に追加することによって) に関連付ける何らかの方法を作成します。次に、キューからノード u をデキューし、ノード v をキューに追加しようとするときはいつでも、v の親ポインタをノード u に設定します。これは、ノード v にたどり着いた方法が、u へのパスをたどり、そのパスを 1 つのエッジで延長して v に到達したことを示しています。
これを実行して BFS を終了したら、宛先ノードから開始し、開始ノードに戻るまで親ポインターを繰り返したどることで、最短パスの逆を読み取ることができます。これを取得したら、このパスを逆にして実際の最短パスに戻すことができます。
お役に立てれば！
于 2013-02-07T00:24:29.010 に答える