1

ダイクストラのアルゴリズムでは、緩和は最大 で m 回呼び出されます(m = #edges)。実際に緩和がm回実行される具体的なグラフの例を見つけようとしています。特定のノードへのより安価なパスが見つかるたびに緩和が発生することは理解していますが、そのようなケースを実際に「視覚化」することはできません。

4

1 に答える 1

1

コメントで述べたように、ツリーは一例です。サイクルの例は、次のエッジを持つ n 個の頂点 (n は奇数) のグラフです。

(1, 2) のコスト 1

(2, 3) のコスト 1

(1, 3) のコスト 10

コスト 1 の (3, 4)

コスト 1 の (4, 5)

(3, 5) のコスト 10

...

(n - 2, n - 1) のコスト 1

(n - 1, n) のコスト 1

(n - 2, n) のコスト 10

頂点 1 からの Dijkstra のアルゴリズムは、常に高価な 1->3、3->5、5->7、7->9、... (n - 2)->n エッジを最初に緩和し、次に長いエッジを見つけます。しかし、より安いパス。

与えられたグラフは、ダイクストラのアルゴリズムでプライオリティ キューが必要な理由の良い例です。ランダム グラフでは、単純なキューを使用し、エッジ緩和のたびに頂点を押し戻すだけで非常に高速に動作する傾向がありますが、この場合、そのようなアルゴリズムは指数関数的に実行されます。

于 2012-11-06T22:05:00.590 に答える