อัลกอริทึม Dijkstra ใน JavaScript

Dijkstra's algorithm เป็นอัลกอริทึมหา shortest paths ระหว่าง nodes ใน weighted graph เราจะใช้ addEdge และ addDirectedEdge methods ใหม่เพื่อเพิ่ม weights ให้ edges เมื่อสร้าง graph มาดูการทำงานของอัลกอริทึมนี้:

• สร้าง distance collection และตั้งค่า distances ของ vertices ทั้งหมดเป็น infinity ยกเว้น source node
• Enqueue source node ใน min-priority queue ด้วย priority 0 เพราะ distance เป็น 0
• เริ่ม loop จน priority queue ว่าง และ dequeue node ที่มี minimum distance
• อัปเดต distances ของ connected nodes ถ้า "current node distance + edge weight < next node distance" แล้ว push node ด้วย distance ใหม่เข้า queue
• ดำเนินต่อจน priority queue ว่าง

อัลกอริทึมนี้ 기본คือ assume ว่าทุก nodes อยู่ระยะ infinity จาก source แล้วเริ่มพิจารณา edges และ track distances จาก source อัปเดตถ้าหา lower cost path

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

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

djikstraAlgorithm(startNode) {
  let distances = {};
  // เก็บ reference ไป previous nodes
  let prev = {};
  let pq = new PriorityQueue(this.nodes.length * this.nodes.length);
  // ตั้ง distances ทุก nodes เป็น infinity ยกเว้น startNode
  distances[startNode] = 0;
  pq.enqueue(startNode, 0);
  this.nodes.forEach(node => {
    if (node !== startNode) distances[node] = Infinity;
    prev[node] = null;
  });
  while (!pq.isEmpty()) {
    let minNode = pq.dequeue();
    let currNode = minNode.data;
    let weight = minNode.priority;
    this.edges[currNode].forEach(neighbor => {
      let alt = distances[currNode] + neighbor.weight;
      if (alt < distances[neighbor.node]) {
        distances[neighbor.node] = alt;
        prev[neighbor.node] = currNode;
        pq.enqueue(neighbor.node, distances[neighbor.node]);
      }
    });
  }
  return distances;
}

ทดสอบการทำงานได้ดังนี้:

ตัวอย่างการใช้งาน

let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");
g.addDirectedEdge("A", "C", 100);
g.addDirectedEdge("A", "B", 3);
g.addDirectedEdge("A", "D", 4);
g.addDirectedEdge("D", "C", 3);
g.addDirectedEdge("D", "E", 8);
g.addDirectedEdge("E", "F", 10);
g.addDirectedEdge("B", "G", 9);
g.addDirectedEdge("E", "G", 50);
console.log(g.djikstraAlgorithm("A"));

ผลลัพธ์

จะได้ผลลัพธ์ดังนี้:

{ A: 0, B: 3, C: 7, D: 4, E: 12, F: 22, G: 12 }