Các thuật toán đường dẫn 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 một đồ thị sao cho tổng trọng số của các cạnh cấu thành của nó là nhỏ nhất. Ở đây, chúng ta cần sửa đổi thêm cạnh của mình và thêm các phương thức có hướng để cho phép thêm trọng số vào các cạnh.

Hãy để chúng tôi xem cách chúng tôi có thể thêm điều này -

Ví dụ

/**
   * 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);
}

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