อัลกอริทึม Floyd-Warshall ใน JavaScript

Dijkstra's algorithm ใช้หา shortest path จาก node หนึ่งไปทุก node อื่นๆ มีกรณีที่เราต้องหา shortest paths จากทุก node ไปทุก node อื่น นี่คือที่มาของ All pairs shortest path algorithms อัลกอริทึมที่ใช้มากที่สุดคือ Floyd Warshall algorithm

Floyd Warshall algorithm ทำงานดังนี้:

• Initialize N x N matrix ของ distances เป็น Infinity
• สำหรับแต่ละ edge u, v อัปเดต matrix ให้แสดง weight ของ edge นี้ และสำหรับ edges v, v อัปเดต weight เป็น 0
• สร้าง 3 nested loops ด้วย iterators i, j, k สำหรับทุก node i's distance ไปทุก node j เราพิจารณาใช้ k เป็น intermediate points และอัปเดต distance ถ้าหาได้น้อยกว่า arr[i][j] ที่มีอยู่

แทนที่จะใช้ matrix เราจะใช้ object เพราะไม่ต้อง track index ถ้าใช้ complex objects แทนแต่ละ node

มาดูการนำไปใช้งาน:

ตัวอย่างโค้ด

floydWarshallAlgorithm() {
  let dist = {};
  for (let i = 0; i < this.nodes.length; i++) {
    dist[this.nodes[i]] = {};
    // สำหรับ existing edges กำหนด dist เท่ากับ weight
    this.edges[this.nodes[i]].forEach(e => (dist[this.nodes[i]][e.node] = e.weight));
    this.nodes.forEach(n => {
      // สำหรับ nodes อื่นๆ กำหนดเป็น infinity
      if (dist[this.nodes[i]][n] == undefined)
        dist[this.nodes[i]][n] = Infinity;
      // สำหรับ self edge กำหนด dist เป็น 0
      if (this.nodes[i] === n) dist[this.nodes[i]][n] = 0;
    });
  }
  this.nodes.forEach(i => {
    this.nodes.forEach(j => {
      this.nodes.forEach(k => {
        // เช็คว่าการไป i ถึง k แล้ว k ถึง j ดีกว่าตรงๆ i ถึง j ไหม
        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 }
}