Shortest Path Algorithms ใน JavaScript

ใน graph theory shortest path problem คือโจทย์หา path ระหว่างสอง vertices (nodes) ใน graph ที่ sum of weights ของ constituent edges ถูก minimize ที่นี่เราต้อง modify add edge และ add directed methods ให้รองรับการเพิ่ม weights ให้ edges ด้วย

มาดูวิธีเพิ่มได้อย่างไร:

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

/**
 * เพิ่ม 2 edges ด้วย weight เดียวกันในทั้งสองทิศทาง
 * weight
 * node1 <================> node2
 * weight
 */
addEdge(node1, node2, weight = 1) {
  this.edges[node1].push({ node: node2, weight: weight });
  this.edges[node2].push({ node: node1, weight: weight });
}
/**
 * เพิ่ม edge ดังนี้:
 * weight
 * node1 ----------------> node2
 */
addDirectedEdge(node1, node2, weight = 1) {
  this.edges[node1].push({ node: node2, weight: weight });
}
display() {
  let graph = "";
  this.nodes.forEach(node => {
    graph += node + "->" + this.edges[node].map(n => n.node).join(", ") + "\n";
  });
  console.log(graph);
}

ตอนนี้เวลา add edge ถ้าไม่ระบุ weight จะมี default weight 1 เราสามารถใช้ implement shortest path algorithms ได้แล้ว