ในทฤษฎีกราฟ ปัญหาเส้นทางที่สั้นที่สุดคือปัญหาในการค้นหาเส้นทางระหว่างจุดยอดสองจุด (หรือโหนด) ในกราฟ โดยที่ผลรวมของน้ำหนักของขอบที่เป็นส่วนประกอบจะลดลง ที่นี่เราจำเป็นต้องแก้ไขขอบเพิ่มของเราและเพิ่มวิธีการโดยตรงเพื่อให้สามารถเพิ่มน้ำหนักให้กับขอบได้เช่นกัน
มาดูกันว่าเราจะเพิ่มสิ่งนี้ได้อย่างไร -
ตัวอย่าง
/**
* Adds 2 edges with the same weight in either direction
*
* 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 });
}
/**
* Add the following 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);
} เมื่อเพิ่มขอบลงในกราฟแล้ว หากเราไม่ระบุน้ำหนัก น้ำหนักเริ่มต้นเป็น 1 จะถูกกำหนดให้กับขอบนั้น ตอนนี้เราใช้สิ่งนี้เพื่อนำอัลกอริธึมพาธที่สั้นที่สุดไปใช้
