3

私のグラフには、頂点をそれ自体に接続するようなエッジが含まれていません。2 つの頂点の間には 1 つのエッジしかありません。ウィキペディアから、与えられた条件に基づいて最短経路を計算するために使用されるアルゴリズムについて知りました。最も有名なアルゴリズムの 1 つは で、Dijkstra's algorithmソース頂点からグラフ内の他のすべての頂点への最短経路を見つけます。
しかし、を使用することDijkstra's algorithmで、すべての頂点を探索する必要はありませんが、私の目標は、単一のソースから単一の目的地までの最短経路を見つけることです。ここでどの戦略を使用する必要がありますか? そのため、他のすべての頂点を探索する必要はありません。

私のアプローチの 1 つは、を使用することbidirectional bfsです。つまり、 から 2つ、 から 1 つをbidirectional bfs適用することを意味します。両方のツリーで初めて同じものを見つけたらすぐに、両方を停止できます。これで、ソースからその子へのパス、子から宛先へのパスが、ソースから宛先への最短パスになります。bfssource nodedestination nodechildbfsunion

しかし、Wikipedia と bidirectional bfsで説明されているすべてのアプローチのうち、どれが私のグラフに最も適しているでしょうか?

4

4 に答える 4

4

使用できる明らかなヒューリスティック関数があるかどうか、またはグラフに関してさらに使用可能な情報がないかどうかによって異なります。

オプションは次のとおりです。

  • BFS：一般的な場合、または計算時間をそれほど気にしない場合。
  • ダイクストラ（ダイクストラは優先キューを備えたBFSです）：エッジに重み/価格（負ではない）があり、CPU時間を気にする場合。
  • A *（A * "is" Dijkstra with heuristic function-たとえば、都市地図上の距離）：平均的な場合に非常に高速にしたいが、優れたヒューリスティック関数を提供する必要がある場合。

一部のグラフの問題では、動的計画法またはその他のアルゴリズムツールを使用できる場合があります。状況によります。詳細については、 http：//community.topcoder.com/tc？module = Static＆d1 = tutorials ＆d2=alg_indexのチュートリアルを参照してください...

于 2012-04-07T11:29:47.090 に答える
1

Introduction to Algorithms (CLRS) second edition, page 581 から:

与えられた頂点とについて、 からuへの最短経路を見つけます。ソース頂点で単一ソースの問題を解決すると、この問題も解決されます。さらに、最悪の場合でも最高の単一ソース アルゴリズムよりも漸近的に高速に実行される、この問題に対するアルゴリズムは知られていません。vuvu

したがって、ダイクストラのアルゴリズムに固執してください:)

于 2012-04-07T11:14:29.440 に答える
0

ダイクストラのアルゴリズムを使用して、これまでに見つけた最短のパスよりもすでに長いパスの探索を停止するように最適化できます。それらは短くならないためです（エッジに負の重みがない場合）。

于 2012-04-07T11:16:15.380 に答える