Thuật toán Dijkstra trong JavaScript

Thuật toán Dijkstra là thuật toán tìm đường đi ngắn nhất giữa các nút trong đồ thị có trọng số. Chúng ta sẽ dùng các phương thức addEdge và addDirectedEdge mới để thêm trọng số cho cạnh khi tạo đồ thị. Hãy xem thuật toán này hoạt động như thế nào:

• Tạo tập hợp khoảng cách và đặt khoảng cách của tất cả đỉnh là infinity trừ nút nguồn.
• Đưa nút nguồn vào hàng đợi ưu tiên min-priority queue với độ ưu tiên 0 vì khoảng cách là 0.
• Bắt đầu vòng lặp cho đến khi hàng đợi ưu tiên rỗng và lấy nút có khoảng cách nhỏ nhất ra.
• Cập nhật khoảng cách của các nút kề với nút vừa lấy ra nếu "khoảng cách nút hiện tại + trọng số cạnh < khoảng cách nút kế tiếp", sau đó đưa nút với khoảng cách mới vào hàng đợi.
• Tiếp tục cho đến khi hàng đợi ưu tiên rỗng.

Thuật toán cơ bản giả định tất cả nút ở khoảng cách vô cực từ nguồn. Sau đó nó bắt đầu xét các cạnh và theo dõi khoảng cách của các nút từ nguồn, cập nhật nếu tìm thấy đường đi chi phí thấp hơn dọc theo đường.

Hãy xem triển khai trong code:

Ví dụ

djikstraAlgorithm(startNode) {
  let distances = {};
  // Lưu tham chiếu đến nút trước
  let prev = {};
  let pq = new PriorityQueue(this.nodes.length * this.nodes.length);
  // Đặt khoảng cách đến tất cả nút là infinity trừ 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;
}

Bạn có thể kiểm tra bằng cách sau:

Ví dụ

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"));

Kết quả

Điều này sẽ cho ra kết quả:

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