グラフ理論は初めてです。ノード (1,1) から開始し、ノード (r,c) に到達する必要があります。つまり、2D デカルト平面として番号が付けられたノードで四角形を想像できます。左上のノードから検索を開始し、右下に到達する必要があります。ノード。あるノードから別のノードへの移動にはある程度の重みがあるため、O(n) で BFS (Breadt First Search) を使用して重み付きグラフの最小コスト パスを解決できますか? BFS で不可能な場合は、別のアルゴリズムを提案してください。事前に感謝します。
1 に答える
2
あなたが初めての場合は、最もよく知られているアルゴリズムであるダイクストラのアルゴリズムを見て、あなたが望むことをするべきです。それを行うために BFS を微調整することもできますが、非常に遅くなります (おそらく、ダイクストラと同じくらい多くのことを行います)。試してみて、問題があれば戻ってきてください
于 2012-11-02T22:52:29.270 に答える