[アルゴリズム]マルチアウトプットアルゴリズム

📌 Dijkstraアルゴリズムとは?
複数のカーブアルゴリズムは、2つの頂点間の最短パスを解く際に使用される最も代表的なナビゲーションアルゴリズムです.2つの頂点間の最短パスに加えて、マルチアウトアルゴリズムは、起点からすべての頂点までの最短パスのアルゴリズムでもある.複数のパスアルゴリズムに入る前に,最短パスの定義と最短パスの特性を理解する.
多翼点アルゴリズムは,起点から別の頂点への最短経路を解く際の有用なアルゴリズムである.
📌 最短パス
最短経路は?
重み付けパターンG=(V,E,W)が存在する場合、頂点xから頂点yまでのあるパスPの重み付け値W(P)が頂点xからyまでのパスの中で最も小さい場合、Pを最短パスと呼ぶ.簡単に言えば、2つの頂点間に存在するパスのうち、重みが最も小さいパスを最短パスと呼ぶ.
最短パスのプロパティ
「最短パスの中には、最短パスで構成されているものもあります.」
頂点xから頂点zまでの最短パスは、(頂点xから頂点yまでの最短パス)+(頂点yから頂点zまでの最短パス)と同じです.頂点から頂点への最短パスは、以前に取得した最短距離情報を使用します.ダイナミックプランニングの特徴は、大きな問題を解決するときに小さな問題を解決することです.

例えば、1から5までの最短経路は、1から4までの最短経路と、4から5までの最短経路との和である.
📌 マルチアウトプットアルゴリズムの最短パス
多出力アルゴリズムの動作原理は以下の通りである.

1. 모든 정점의 방문 정보를 초기화 합니다.
2. 정점 중 출발점을 선택합니다. 출발점은 Tree Set에 저장하고, 그와 인접한 정점의 정보를 Fringe Set에 저장합니다.
3. Fringe Set에서 최소값을 갖는 정점을 Tree Set에 추가하고, 그 정점의 인접한 정점의 정보를 Fringe Set에 업데이트 합니다.
	- 업데이트 방식은 새로운 정점 정보가 들어오면 추가하고, 기존에 정점 정보가 이미 있다면, 가중치가 작은 경우에만 업데이트 합니다.
4. 그래프의 모든 정점이 Tree Set으로 전환될 때 까지 3번의 과정을 반복합니다.

* fringe set / vertex : 인접한 정점들 중 아직 방문하지 않은 정점을 의미합니다.

例を見てみましょう.

次の図では、始点が1の場合、始点が1のツリーセットです.隣接する2番6番7番はFrange Setです

왼쪽 영역 : Tree Set / 오른쪽 영역 : Fringe Set

FringSetで最も重みの小さい頂点を選択する必要があります.これにより、2番目の頂点がツリーセットに追加されます.次に、2番目の頂点に隣接する頂点がFrange Setに更新されます.

1番と2番の頂点は7番に隣接しています.この場合、Fringe Setは、より小さな頂点を選択することによって更新される.したがって、第2および第7の幹線の情報は保存されず、第1および第7の幹線の情報のみが保存される.

上記の手順を繰り返すと、すべての頂点にアクセスし、すべてのエクスポートアルゴリズムを実行します.
📌 マルチアウトレットアルゴリズム解析
マルチアウトアルゴリズムでは、すべての頂点にアクセスする必要があります.したがって、N回の実行が必要であり、Heap構造ではlognでナビゲートできます.従って,マルチアウトプットアルゴリズムの時間的複雑度はO(N*logn)である.

📌 の最後の部分
今日,最短経路を求める際に用いられるアルゴリズム:マルチアウトプットアルゴリズムについて議論した.時間的複雑さは隣接リストと隣接マトリクスの実施に依存するため、幹線情報が少ない場合は隣接リストとして実施することが望ましい.