Thuật toán Dijkstra trong Javascript

Thuật toán Dijkstra là một thuật toán để tìm đường đi ngắn nhất giữa các nút trong một đồ thị có trọng số. Chúng tôi sẽ sử dụng các phương thức addEdge và addDiirectEdge mới để thêm trọng số vào các cạnh khi tạo biểu đồ. Hãy cùng chúng tôi xem xét cách thức hoạt động của thuật toán này -

• Tạo tập hợp khoảng cách và đặt tất cả các khoảng cách đỉnh là vô cùng ngoại trừ nút nguồn.
• Xếp thứ tự nút nguồn trong hàng đợi có mức độ ưu tiên tối thiểu với mức độ ưu tiên 0 vì khoảng cách là 0.
• Bắt đầu một vòng lặp cho đến khi hàng đợi ưu tiên trống và xếp hàng lại nút với khoảng cách tối thiểu từ nó.
• Cập nhật khoảng cách của các nút được kết nối với nút bật lên nếu "khoảng cách nút hiện tại + trọng số cạnh
• Tiếp tục cho đến khi hàng đợi ưu tiên trống.

Điều mà thuật toán này thực hiện về cơ bản là giả sử tất cả các nút đều ở khoảng cách vô hạn so với nguồn. Sau đó, nó bắt đầu xem 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 giống nhau nếu nó tìm thấy đường dẫn chi phí thấp hơn trên đường đi.

Hãy để chúng tôi xem xét triển khai này trong mã -

Ví dụ

djikstraAlgorithm(startNode) {
   let distances = {};

   // Stores the reference to previous nodes
   let prev = {};
   let pq = new PriorityQueue(this.nodes.length * this.nodes.length);

   // Set distances to all nodes to be infinite except 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 điều này bằng cách sử dụng -

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

Đầu ra

Điều này sẽ cung cấp đầu ra -

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