Javascriptの最短経路アルゴリズム

グラフ理論では、最短経路問題は、構成するエッジの重みの合計が最小になるように、グラフ内の2つの頂点（またはノード）間のパスを見つける問題です。ここでは、エッジの追加と有向メソッドの追加を変更して、エッジにも重みを追加できるようにする必要があります。

これを追加する方法を見てみましょう-

例

/**
   * Adds 2 edges with the same weight in either direction
   *
   *             weight
   * node1 <================> node2
   *             weight
   *
*/
addEdge(node1, node2, weight = 1) {
   this.edges[node1].push({ node: node2, weight: weight });
   this.edges[node2].push({ node: node1, weight: weight });
}

/**
   *  Add the following edge:
   *
   *             weight
   * node1 ----------------> node2
   *
*/

addDirectedEdge(node1, node2, weight = 1) {
   this.edges[node1].push({ node: node2, weight: weight });
}

display() {
   let graph = "";
   this.nodes.forEach(node => {
      graph += node + "->" + this.edges[node].map(n => n.node) .join(", ")+ "\n";
   });
   console.log(graph);
}

これで、グラフにエッジを追加するときに、重みを指定しない場合、デフォルトの重み1がそのエッジに割り当てられます。これを使用して、最短経路アルゴリズムを実装できるようになりました。