Javascript의 Floyd-Warshall 알고리즘

Djikstra의 알고리즘은 한 노드에서 다른 모든 노드까지의 최단 경로 거리/경로를 찾는 데 사용됩니다. 모든 노드에서 다른 모든 노드까지의 최단 경로를 찾아야 하는 경우가 있습니다. 여기에서 모든 쌍 최단 경로 알고리즘이 유용합니다. 가장 많이 사용되는 모든 쌍 최단 경로 알고리즘은 Floyd Warshall 알고리즘입니다.

Floyd Warshall 알고리즘은 다음과 같이 작동합니다 -

• N x N 거리 행렬을 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 }
}