Thuật toán Floyd-Warshall trong Javascript

Thuật toán của Djikstra được sử dụng để tìm khoảng cách / đường đi của đường đi ngắn nhất từ ​​một nút đến tất cả các nút khác. Có những trường hợp chúng ta cần tìm đường đi ngắn nhất từ ​​tất cả các nút đến tất cả các nút khác. Đây là nơi mà các thuật toán đường đi ngắn nhất của Tất cả các cặp có ích. Thuật toán đường đi ngắn nhất cho tất cả các cặp được sử dụng nhiều nhất là thuật toán Floyd Warshall.

Thuật toán Floyd Warshall hoạt động như sau -

• Chúng tôi khởi tạo ma trận N x N khoảng cách là Vô cực.
• Sau đó, đối với mỗi cạnh u, v, chúng tôi cập nhật ma trận này để hiển thị trọng số của cạnh này và đối với các cạnh v, v, chúng tôi cập nhật trọng số là 0.
• Chúng tôi tạo 3 vòng lặp lồng nhau với các trình vòng lặp I, j và k. đối với mọi khoảng cách của nút I đến mọi nút j, chúng tôi coi việc sử dụng k làm điểm trung gian và cập nhật khoảng cách nếu chúng tôi tìm thấy một khoảng cách nhỏ hơn arr [i] [j] hiện có.

Thay vì sử dụng ma trận, chúng tôi sẽ sử dụng một đối tượng vì chúng tôi không cần theo dõi chỉ mục trong trường hợp chúng tôi đang sử dụng các đối tượng phức tạp để đại diện cho mỗi nút.

Bây giờ chúng ta hãy xem xét việc triển khai tương tự -

Ví dụ

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;
   }
}

Bạn có thể kiểm tra điều này bằng cách sử dụng -

Ví dụ

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());

Đầu ra

Điều này sẽ cung cấp đầu ra -

{
   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 }
}