อัลกอริทึมของ Djikstra ใช้เพื่อค้นหาระยะทาง/เส้นทางของเส้นทางที่สั้นที่สุดจากโหนดหนึ่งไปยังโหนดอื่นทั้งหมด มีหลายกรณีที่เราต้องค้นหาเส้นทางที่สั้นที่สุดจากโหนดทั้งหมดไปยังโหนดอื่นทั้งหมด นี่คือจุดที่อัลกอริธึมพาธที่สั้นที่สุดของ All pairs มีประโยชน์ อัลกอริธึมพาธที่สั้นที่สุดของทุกคู่ที่ใช้มากที่สุดคืออัลกอริธึม Floyd Warshall
อัลกอริธึม Floyd Warshall ทำงานดังนี้ -
- เราเริ่มต้นเมทริกซ์ N x N ของระยะทางให้เป็นอนันต์
- จากนั้นสำหรับแต่ละขอบ u, v เราอัปเดตเมทริกซ์นี้เพื่อแสดงน้ำหนักของขอบนี้ และสำหรับขอบ v, v เราอัปเดตน้ำหนักเป็น 0
- เราสร้าง 3 ลูปซ้อนกันด้วยการวนซ้ำ I, j และ k สำหรับทุกๆ โหนด 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 }
} 