Thuật toán Floyd-Warshall trong JavaScript

Thuật toán Dijkstra dùng để tìm khoảng đường/đường đi ngắn nhất từ một nút đến tất cả các nút khác. Có trường hợp cần tìm đường đi ngắn nhất từ tất cả nút đến tất cả nút khác. Đây là lúc thuật toán All-pairs shortest path (đường đi ngắn nhất mọi cặp) hữu ích. Thuật toán phổ biến nhất là Floyd-Warshall.

Floyd-Warshall hoạt động như sau:

• Khởi tạo ma trận khoảng cách N x N là Infinity.
• Sau đó với mỗi cạnh u, v, cập nhật ma trận này để thể hiện trọng số của cạnh đó và với cạnh v, v cập nhật trọng số là 0.
• Tạo 3 vòng lặp lồng nhau với biến lặp i, j, k. Với khoảng cách từ nút i đến mọi nút j, xem xét dùng k làm điểm trung gian và cập nhật khoảng cách nếu tìm thấy nhỏ hơn arr[i][j] hiện tại.

Thay vì dùng ma trận, ta sẽ dùng object vì không cần theo dõi chỉ số trong trường hợp dùng đối tượng phức tạp biểu diễn mỗi nút.

Hãy xem triển khai cụ thể:

Ví dụ

floydWarshallAlgorithm() {
  let dist = {};
  for (let i = 0; i < this.nodes.length; i++) {
    dist[this.nodes[i]] = {};
    // Với cạnh hiện có gán khoảng cách bằng trọng số
    this.edges[this.nodes[i]].forEach(e => (dist[this.nodes[i]][e.node] = e.weight));
    this.nodes.forEach(n => {
      // Với tất cả nút khác gán là infinity
      if (dist[this.nodes[i]][n] == undefined)
        dist[this.nodes[i]][n] = Infinity;
      // Với cạnh tự thân gán khoảng cách là 0
      if (this.nodes[i] === n) dist[this.nodes[i]][n] = 0;
    });
  }
  this.nodes.forEach(i => {
    this.nodes.forEach(j => {
      this.nodes.forEach(k => {
        // Kiểm tra đi từ i đến k rồi k đến j có tốt hơn
        // không so với đi trực tiếp từ i đến j. Nếu có thì cập nhật
        // giá trị i đến j thành giá trị mới
        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 bằng cách sau:

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

Kết quả

Điều này sẽ cho ra kết quả:

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