5

Dijkstra のアルゴリズムの実装では、すべてのノードを含む 1 つの配列と、すべてのノードを含む 1 つの優先キューがあります。ノードがデキューされるたびに、隣接するすべてのノードを新しい距離とそれがどこから来たかで更新するので、パスをバックトラックできます。

プライオリティ キュー内のノードは新しい距離で更新され、配列内のノードは元の場所と新しい距離で更新されます。ノードがデキューされると、配列内の最終距離が更新されます。

  PathInfo current = pq.remove();
  path[current.pos].distance = current.distance;

前のノードに関する情報で配列を更新し、距離で優先キューを更新することは許容されますか?

これは、より適切な距離が見つかるたびに発生します。

      PathInfo key(i, newDistance);
      path[i].distance = newDistance;
      path[i].previous = current.pos;
      pq.decreaseKey(key);

基本的に同じ情報でアレイとプライオリティ キューを更新するのは少し冗長に思えます。

現在、PQ のデータ構造として通常の配列を使用しています。優先度の更新は線形時間で行われ、デキューも線形時間で行われます。

プライオリティ キューではどのデータ構造を使用すればよいですか? また、ノードのプライオリティを変更するにはどうすればよいですか?

私はC++を使用しています

4

2 に答える 2

1

ここには2種類の距離があります。優先キューには更新の対象となる「暫定距離」があり、配列には更新されない「最終距離」があります（ダイクストラのアルゴリズムでは、削除されたノードを更新する必要がないため）。優先キュー）。

アレイの距離を不必要に更新しているようです。おそらく、配列ノードのフィールド名を変更して、これを文書化することもお勧めします：arrayNode.distanceからarrayNode.finalDistance。

言い換えると、配列ノードを使用してダイクストラのアルゴリズムからの結果を出力しているようです。したがって、優先キューから削除されたときに、各配列ノードの距離を1回だけ設定する必要があります。

優先度キューの実装で、特定のキーに関連付けられている現在の距離を照会する機能が提供されていない場合は、そのdecreaseKey()動作の動作を確認してください。decreaseKey()新しい優先度が実際に低下しない更新を操作が拒否する場合は、自分でそのチェックを実行する必要はありません。現在のノードのネイバーごとに呼び出すことができます。

ただし、decreaseKey()関数がそのケースを正しく処理せず、そのチェックを手動で実行できる補助クエリ関数がなく、どちらの欠陥も修正する機会がない場合は、その目的のために冗長な情報を維持する必要があります...。

于 2013-02-19T20:56:29.083 に答える
0

使用できるデータ構造:

たぶん、配列で最小のものを見つけるための他のもの。

ノードの優先度を更新するときは、好みのデータ構造も同期する必要があります。

注:マトリックスを使用して接続されたノードをチェックした場合、アルゴリズムの複雑さは変わらないため、単純にデータ構造を使用しない可能性があります。I は引き続き O(N^2) になります (適切な優先順位を持つノードを見つけるために直接サイクルを使用します)。グラフには多くのノードと少量の接続があり、接続されたノードのリストとして保存されます (放電グラフ)

于 2013-02-19T14:36:10.977 に答える