Các thuật toán đường đi ngắn nhất trong JavaScript

Trong lý thuyết đồ thị, bài toán đường đi ngắn nhất là bài toán tìm đường đi giữa hai đỉnh (hoặc nút) trong đồ thị sao cho tổng trọng số các cạnh cấu thành được tối thiểu. Ở đây cần sửa đổi phương thức addEdge và addDirected để cho phép thêm trọng số cho cạnh.

Hãy xem cách thêm điều này:

Ví dụ

/**
 * Thêm 2 cạnh cùng trọng số theo 2 chiều
 * 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 });
}
/**
 * Thêm cạnh có hướng:
 * 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);
}

Bây giờ khi thêm cạnh vào đồ thị, nếu không chỉ định trọng số, trọng số mặc định 1 sẽ được gán cho cạnh đó. Ta có thể dùng này để triển khai các thuật toán đường đi ngắn nhất.