1.Dijkstraアルゴリズム

そうだ.その有名なマルチタスクアルゴリズムです.これは最短距離を探す過程です.これもグリディアルゴリズムの一種です.
ダエストラというオランダのプログラマーは、アムステルダムから別の駅までの最短距離を計算するのに20分かかり、その結果、世界で非常に多くのアルゴリズムが使われているアルゴリズムを提案した.本当に起きられない
このアルゴリズムは基本的に重み付け図であるべきである.最短距離を計算するため、edgeにのみ値を割り当てることができます.
したがって、A−>Eの最短距離を探す場合、各プロセス(A−>D/D−>E)に必要な距離を計算せざるを得ない.そして、このアルゴリズムには大きな理由があります.A->Eまでの最短距離を求めると,すべてのノードからAまでの最短距離が同時に発見される.
では、まず実行手順を見てみましょう.

2.アルゴリズム実行プロセス

まずグラフを作りましょう.今回はweight(距離,edgeValue)を追加する必要があり,追加時にobjを押す必要がある.

class Weighted {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(val) {
    if (!this.adjacencyList[val]) {
      this.adjacencyList[val] = [];
    }
  }

  addEdge(v1, v2, weight) {
    this.adjacencyList[v1].push({ node: v2, weight });
    this.adjacencyList[v2].push({ node: v1, weight });
  }

  // 나머지 메소드는 거의 비슷해서 생략하겠다
}

var weightedGraph = new Weighted();
weightedGraph.addVertex("a");
weightedGraph.addVertex("b");
weightedGraph.addVertex("c");
weightedGraph.addVertex("d");
weightedGraph.addVertex("e");
weightedGraph.addVertex("f");

weightedGraph.addEdge("a", "b", 4);
weightedGraph.addEdge("a", "c", 2);
weightedGraph.addEdge("c", "d", 2);

weightedGraph.addEdge("c", "f", 4);
weightedGraph.addEdge("b", "e", 3);
weightedGraph.addEdge("d", "e", 3);
weightedGraph.addEdge("d", "f", 1);
weightedGraph.addEdge("e", "f", 1);

次に、vtxをそれぞれ追加してweightを設定すると、下図が得られます.

そしてAからEまでの最短距離どんなアルゴリズムを通りますか?
まず英語の方法を見てみましょう.

The Approach

First we choose start point and destination.

Every time we look to visit a new node, we pick the node with the smallest known distance to visit first. (using priority queue dequeue)

After we chose which node to visit, we mark the node as visited.

Once we’ve moved to the node we’re going to visit, we look at each of its neighbors.

For each neighboring node, we calculate the distance by summing the total edges that lead to the node we’re checking from the starting node.

If the new total distance to a node is less than the previous total, we store the new shorter distance for that node. and we also update very previous node to that node to get to the starting point. (update only if we find the shortest way).

Keep doing until what we picked up is desitination node.

まず始点と終点を選択します.(A->E)

VisitedにAを追加し、Aと近隣の距離を計算し、Distanceテーブルに追加します.

新しく計算した距離が追加した距離より小さい場合:

の距離で新しい距離を更新します.

およびPreviousでAが通過する必要がある直接ノードでは、直前のノードが直ちに更新される.

次に、距離テーブルの距離が最小になるノードを選択します.

選択したノードの隣接ノードとA間の距離を計算します.

上記の手順を繰り返します.いつまでですか.Eまで引く

3.表で表示します。

やはり表で見てみましょう.
まずVistade/Distance/Perviousの3種類のobjを作成します.
まずAは開始点であり,vistedに追加され,距離は0である.そして残りの距離はまずInfinity、前もnullとします.
そしてAの隣がBとCなので、BとCからAの距離を測ります.
すべてのdistanceは登録された距離よりも小さいため、distanceで更新され、preferenceでも更新されます.
それからdistanceを見て、最初のvtxを除いて、最小の距離はCです.では、Cを選択します.
Cをアクセスに保存し、Cの隣人を表示します.そのAは既にアクセスしており、DとFの距離を測るだけで済みます.
DとFの最短距離CからAまでの距離はそれぞれ4,6である.では、distanceに登録されている最短距離よりも、書いておくと更新されます.そして以前も更新していました.今回Aが通るVTXに行くのですが、前のVTXはCです.だからCに登録しましょう.
また,非アクセスノードでは,距離が最も小さいのはBとDであり,Bからである.
アクセスにBを追加します.そしてお隣さんを見るとAさんとEさんですがAさんはすでに訪問しているのでEさんだけ訪問すればいいです
EからBからAまでの最短距離は7です.では、Distanceに登録されているEを見てみましょう.無限なので、7はもっと小さいです.
したがって、distanceおよびpreferenceに登録し、distanceで最小の数値を検索します.Dです.Dを訪問者の中に置いて、隣人を見てみましょう.
C,E,F.このうちアクセスしていないノードはE,Fである.DからAまでの最短距離を求める.ではEは7、Fは5です.distanceと比較してEは7距離登録されているので続行します.逆にFは6なのでdistanceとpreferenceを更新します.
このようにして選ばれたNODEは、目的地であるEまで行われるこれで次の表が完成しました.

var visited = [A, C, B, D, F];

VtxShortest path from AA0BInfinity 4CInfinity 2DInfinity 4EInfinity 7 6FInfinity 6 5
VtxPrevious Node to get to AAnullBnull ACnull ADnull CEnull B FFnull C D
だからEに行く最短距離は6で、通るVTXは前を見ることができます.E->F->D->C->A.これを逆にすればいい
初めて接するときはとても複雑で、手で描く過程で何度も試してみなければなりません.それは慣れました.相変わらず.
では、次の文章で実際のコードを書きましょう.