JavascriptのFloyd-Warshallアルゴリズム

Djikstraのアルゴリズムは、1つのノードから他のすべてのノードまでの最短経路の距離/経路を見つけるために使用されます。すべてのノードから他のすべてのノードへの最短パスを見つける必要がある場合があります。ここで、すべてのペアの最短経路アルゴリズムが役立ちます。最も使用されているすべてのペアの最短経路アルゴリズムは、FloydWarshallアルゴリズムです。

フロイドウォーシャルアルゴリズムは次のように機能します-

• 距離のNxN行列をInfinityに初期化します。
• 次に、各エッジu、vについて、この行列を更新してこのエッジの重みを表示し、エッジv、vについては、重みを0に更新します。
• イテレータI、j、kを使用して3つのネストされたループを作成します。すべてのノードIからすべてのノードjまでの距離について、kを中間点として使用することを検討し、既存のarr[i][j]よりも小さい距離が見つかった場合は距離を更新します。

複雑なオブジェクトを使用して各ノードを表す場合に備えて、インデックスを追跡する必要がないため、マトリックスを使用する代わりに、オブジェクトを使用します。

次に、同じ-

例

floydWarshallAlgorithm() {
   let dist = {};
   for (let i = 0; i < this.nodes.length; i++) {
      dist[this.nodes[i]] = {};
      // For existing edges assign the dist to be same as weight
      this.edges[this.nodes[i]].forEach(e => (dist[this.nodes[i]][e.node] = e.weight));
      this.nodes.forEach(n => {
         // For all other nodes assign it to infinity
         if (dist[this.nodes[i]][n] == undefined)
         dist[this.nodes[i]][n] = Infinity;
         // For self edge assign dist to be 0
         if (this.nodes[i] === n) dist[this.nodes[i]][n] = 0;
      });
   }
   this.nodes.forEach(i => {
      this.nodes.forEach(j => {
         this.nodes.forEach(k => {
            // Check if going from i to k then from k to j is better
            // than directly going from i to j. If yes then update
            // i to j value to the new value
            if (dist[i][k] + dist[k][j] < dist[i][j])
               dist[i][j] = dist[i][k] + dist[k][j];
            });
         });
      });
      return dist;
   }
}

-

例

let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");

g.addEdge("A", "C", 100);
g.addEdge("A", "B", 3);
g.addEdge("A", "D", 4);
g.addEdge("D", "C", 3);

console.log(g.floydWarshallAlgorithm());

出力

これにより、出力が得られます-

{
   A: { C: 7, B: 3, D: 4, A: 0 },
   B: { A: 3, B: 0, C: 10, D: 7 },
   C: { A: 7, D: 3, B: 10, C: 0 },
   D: { A: 4, C: 3, B: 7, D: 0 }
}