Thuật toán Dijkstra là một trong những thuật toán phổ biến để tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác trong một đồ thị có trọng số. Dưới đây là cách thực hiện thuật toán Dijkstra trong JavaScript.
Mã Nguồn:
class PriorityQueue {
constructor() {
this.values = [];
}
enqueue(val, priority) {
this.values.push({ val, priority });
this.sort();
}
dequeue() {
return this.values.shift();
}
sort() {
this.values.sort((a, b) => a.priority - b.priority);
}
}
class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(vertex) {
if (!this.adjacencyList[vertex]) {
this.adjacencyList[vertex] = [];
}
}
addEdge(vertex1, vertex2, weight) {
this.adjacencyList[vertex1].push({ node: vertex2, weight });
this.adjacencyList[vertex2].push({ node: vertex1, weight });
}
dijkstra(start, finish) {
const nodes = new PriorityQueue();
const distances = {};
const previous = {};
let path = [];
let smallest;
// Initialize distances and priority queue
for (let vertex in this.adjacencyList) {
if (vertex === start) {
distances[vertex] = 0;
nodes.enqueue(vertex, 0);
} else {
distances[vertex] = Infinity;
nodes.enqueue(vertex, Infinity);
}
previous[vertex] = null;
}
// While there are nodes to visit
while (nodes.values.length) {
smallest = nodes.dequeue().val;
if (smallest === finish) {
// Build path to return at end
while (previous[smallest]) {
path.push(smallest);
smallest = previous[smallest];
}
break;
}
if (smallest || distances[smallest] !== Infinity) {
for (let neighbor in this.adjacencyList[smallest]) {
let nextNode = this.adjacencyList[smallest][neighbor];
let candidate = distances[smallest] + nextNode.weight;
let nextNeighbor = nextNode.node;
if (candidate < distances[nextNeighbor]) {
distances[nextNeighbor] = candidate;
previous[nextNeighbor] = smallest;
nodes.enqueue(nextNeighbor, candidate);
}
}
}
}
return path.concat(smallest).reverse();
}
}
// Khởi tạo đồ thị và thêm các cạnh
let graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addVertex('F');
graph.addEdge('A', 'B', 4);
graph.addEdge('A', 'C', 2);
graph.addEdge('B', 'E', 3);
graph.addEdge('C', 'D', 2);
graph.addEdge('C', 'F', 4);
graph.addEdge('D', 'E', 3);
graph.addEdge('D', 'F', 1);
graph.addEdge('E', 'F', 1);
// Tìm đường đi ngắn nhất từ 'A' đến 'E'
console.log(graph.dijkstra('A', 'E')); // Output: [ 'A', 'C', 'D', 'F', 'E' ]
Giải Thích:
-
PriorityQueue Class:
- enqueue(val, priority): Thêm một phần tử vào hàng đợi ưu tiên với giá trị và mức độ ưu tiên.
- dequeue(): Lấy phần tử có mức độ ưu tiên cao nhất (nhỏ nhất) ra khỏi hàng đợi.
- sort(): Sắp xếp lại hàng đợi theo mức độ ưu tiên.
-
Graph Class:
- addVertex(vertex): Thêm một đỉnh vào đồ thị.
- addEdge(vertex1, vertex2, weight): Thêm một cạnh có trọng số giữa hai đỉnh.
-
dijkstra(start, finish):
- Khởi tạo: Tạo hàng đợi ưu tiên, đặt khoảng cách từ đỉnh bắt đầu đến chính nó bằng 0, và tất cả các đỉnh khác bằng vô cực.
- Thuật toán: Lặp qua hàng đợi ưu tiên, cập nhật khoảng cách đến các đỉnh kề và lưu lại đường đi ngắn nhất.
- Kết quả: Trả về đường đi ngắn nhất từ đỉnh bắt đầu đến đỉnh kết thúc.
Tổng Quan:
- Dijkstra: Thuật toán Dijkstra tìm đường đi ngắn nhất trong đồ thị có trọng số.
- Hàng Đợi Ưu Tiên: Sử dụng hàng đợi ưu tiên để quản lý các đỉnh cần thăm theo thứ tự khoảng cách ngắn nhất hiện tại.
- Khoảng Cách: Cập nhật khoảng cách ngắn nhất đến mỗi đỉnh và lưu lại đỉnh trước đó để xây dựng đường đi ngắn nhất.
Ưu Điểm và Hạn Chế:
- Ưu Điểm: Tìm đường đi ngắn nhất hiệu quả trong đồ thị có trọng số dương.
- Hạn Chế: Không xử lý được đồ thị có trọng số âm.
Ví Dụ Thực Tế:
// Khởi tạo đồ thị và thêm các cạnh
let graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addVertex('F');
graph.addEdge('A', 'B', 4);
graph.addEdge('A', 'C', 2);
graph.addEdge('B', 'E', 3);
graph.addEdge('C', 'D', 2);
graph.addEdge('C', 'F', 4);
graph.addEdge('D', 'E', 3);
graph.addEdge('D', 'F', 1);
graph.addEdge('E', 'F', 1);
// Tìm đường đi ngắn nhất từ 'A' đến 'E'
console.log(graph.dijkstra('A', 'E')); // Output: [ 'A', 'C', 'D', 'F', 'E' ]
Trong ví dụ trên, thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh 'A' đến đỉnh 'E' trong đồ thị có trọng số.
Comments