Thuật toán Dijkstra: Tìm đường đi ngắn nhất với Typescript
Thuật toán Dijkstra là một thuật toán dùng để tìm đường đi ngắn nhất từ một điểm xuất phát đến các điểm khác trong đồ thị có trọng số dương
Thời sinh viên, bài toán tìm đường đi ngắn nhất giữa các điểm trong một đồ thị là một trong những bài toán kinh điển. Có nhiều thuật toán khác nhau để giải quyết bài toán này, nhưng phổ biến nhất là thuật toán Dijkstra.
Trong bài viết này, cùng mình đi tìm hiểu về thuật toán Dijkstra, cách hoạt động của nó, triển khai thuật toán này với TypeScript nhé.
1. Thuật Toán Dijkstra Là Gì?
Thuật toán Dijkstra là một thuật toán nổi tiếng dùng để tìm đường đi ngắn nhất từ một điểm xuất phát đến các điểm khác trong đồ thị có trọng số dương, được phát minh bởi nhà toán học người Hà Lan Edsger Dijkstra vào năm 1956.
Điểm đặc biệt của thuật toán Dijkstra là hoạt động theo nguyên tắc "tham lam" (greedy algorithm), nghĩa là sẽ luôn chọn con đường tốt nhất ở hiện tại mà không cần biết đến những quyết định trong tương lai. Nhờ nguyên tắc này, thuật toán Dijkstra giúp giảm thời gian xử lý và tìm ra đường đi ngắn nhất cách hiệu quả.
2. Cách Hoạt Động Của Thuật Toán Dijkstra
Thuật toán Dijkstra hoạt động bằng cách sử dụng hàng đợi ưu tiên (priority queue) để lựa chọn đỉnh có khoảng cách ngắn nhất từ đỉnh xuất phát. Mỗi lần, nó tìm đỉnh có khoảng cách ngắn nhất và sau đó cập nhật khoảng cách từ đỉnh này đến các đỉnh lân cận.
Quá trình thuật toán diễn ra như thế này:
- Khởi tạo khoảng cách từ điểm xuất phát đến tất cả các đỉnh khác là vô cùng lớn (∞), ngoại trừ điểm xuất phát - khoảng cách bằng 0.
- Tìm đỉnh có khoảng cách nhỏ nhất (trong số các đỉnh chưa được thăm) và đánh dấu đỉnh đó thành đã thăm.
- Cập nhật khoảng cách của các đỉnh kề với đỉnh vừa chọn. Nếu tìm được đường đi ngắn hơn thông qua đỉnh này, cập nhật lại khoảng cách của đỉnh kề.
- Lặp lại quá trình này cho đến khi tất cả các đỉnh đã được thăm hoặc không còn đỉnh nào có thể cập nhật.
Hãy hình dung như bạn đang tìm đường đi trên bản đồ: bạn bắt đầu từ một điểm, lần lượt kiểm tra các con đường gần nhất, sau đó cập nhật quãng đường đi ngắn hơn nếu tìm được.
Với ví dụ mình có thể hiện ở phía trên, dựa trên cơ chế hoạt động thì quy trình được diễn ra như sau:
Bước khởi tạo:
- Khoảng cách từ đỉnh 0 đến chính nó là 0.
- Tất cả các đỉnh khác đều có khoảng cách ban đầu là ∞.
Bắt đầu từ đỉnh 0:
- Đỉnh 0 đến đỉnh 1: khoảng cách là 3.
- Đỉnh 0 đến đỉnh 2: khoảng cách là 2.
- Đỉnh 0 đến đỉnh 3: khoảng cách là 3.
Tiếp tục từ đỉnh có khoảng cách nhỏ nhất (đỉnh 2):
- Từ đỉnh 2, có một cạnh nối đến đỉnh 3 với trọng số 4.
- Khoảng cách từ đỉnh 0 đến đỉnh 3 thông qua đỉnh 2 là 2 + 4 = 6. Khoảng cách này lớn hơn khoảng cách trực tiếp từ đỉnh 0 đến đỉnh 3 (3), vì thế sẽ không cập nhật.
- Đỉnh 2 cũng kết nối với đỉnh 1 với trọng số 2. Khoảng cách từ đỉnh 0 đến đỉnh 1 qua đỉnh 2 là 2 + 2 = 4, không ngắn hơn đường đi hiện tại từ đỉnh 0 đến đỉnh 1 (3), nên không cập nhật.
Tiếp tục từ đỉnh có khoảng cách nhỏ nhất tiếp theo (đỉnh 1):
- Đỉnh 1 có các cạnh nối đến đỉnh 2, 3, và 4:
- Khoảng cách từ đỉnh 1 đến đỉnh 3 là 3 + 2 = 5 , nhưng khoảng cách trực tiếp từ đỉnh 0 đến đỉnh 3 là 3, nên không cập nhật.
- Khoảng cách từ đỉnh 1 đến đỉnh 4 là 3 + 1 = 4 , cập nhật khoảng cách từ đỉnh 0 đến đỉnh 4 là 4.
Tiếp tục từ đỉnh 3:
- Khoảng cách từ đỉnh 3 đến đỉnh 4 là 3 + 5 = 8, lớn hơn khoảng cách trước đó (4), do đó không cần cập nhật.
Cuối cùng là đỉnh 4: không còn cập nhật nào.
Vậy đường đi ngắn nhất từ 0 đến 4 là: 0 → 1 → 4 với trọng số là 4.
3. Thuật Toán Dijkstra Với Typescript
Để hiểu rõ hơn về thuật toán Dijkstra, mình sẽ triển khai nó bằng TypeScript. Trước khi bắt đầu, hãy xác định một số giả định cho bài toán của chúng ta.
- Đồ thị của chúng ta sẽ được biểu diễn dưới dạng danh sách kề (adjacency list).
- Các đỉnh được biểu diễn bằng số nguyên dương.
- Trọng số của các cạnh là các số thực dương.
Bây giờ, mình sẽ triển khai thuật toán. Để dễ hiểu hơn, sẽ làm theo từng bước.
3.1 Khởi Tạo Đồ Thị
Cần một cách để biểu diễn đồ thị. Với TypeScript, mình sẽ sử dụng một đối tượng (object) hoặc một Map để lưu trữ danh sách kề.
type Graph = { [key: number]: { node: number; weight: number }[] };
const graph: Graph = {
0: [{ node: 1, weight: 4 }, { node: 2, weight: 1 }],
1: [{ node: 3, weight: 1 }],
2: [{ node: 1, weight: 2 }, { node: 3, weight: 5 }],
3: []
};Ở đây, mình có một đồ thị với 4 đỉnh, mỗi đỉnh được kết nối với các đỉnh khác bằng cạnh có trọng số tương ứng.
3.2 Hàng Đợi Ưu Tiên
Thuật toán Dijkstra yêu cầu một hàng đợi ưu tiên để tìm đỉnh có khoảng cách nhỏ nhất cách hiệu quả. Trong TypeScript, mình sử dụng mảng và sắp xếp lại khi cần.
Tuy nhiên, để tối ưu hơn, mình sẽ sử dụng min-heap hoặc hàng đợi. Dưới đây là code đơn giản.
class PriorityQueue {
private values: { node: number; priority: number }[];
constructor() {
this.values = [];
}
enqueue(node: number, priority: number) {
this.values.push({ node, priority });
this.sort();
}
dequeue() {
return this.values.shift();
}
sort() {
this.values.sort((a, b) => a.priority - b.priority);
}
isEmpty() {
return this.values.length === 0;
}
}3.3 Triển Khai Thuật Toán Dijkstra
Sau khi đã có biểu diễn đồ thị và hàng đợi ưu tiên, chúng ta có thể triển khai thuật toán Dijkstra.
function dijkstra(graph: Graph, start: number): { [key: number]: number } {
const distances: { [key: number]: number } = {};
const priorityQueue = new PriorityQueue();
const previous: { [key: number]: number | null } = {};
for (let node in graph) {
if (parseInt(node) === start) {
distances[node] = 0;
priorityQueue.enqueue(parseInt(node), 0);
} else {
distances[node] = Infinity;
}
previous[node] = null;
}
while (!priorityQueue.isEmpty()) {
const smallest = priorityQueue.dequeue();
const currentNode = smallest?.node;
if (currentNode !== undefined) {
graph[currentNode].forEach(neighbor => {
const candidate = distances[currentNode] + neighbor.weight;
if (candidate < distances[neighbor.node]) {
distances[neighbor.node] = candidate;
previous[neighbor.node] = currentNode;
priorityQueue.enqueue(neighbor.node, candidate);
}
});
}
}
return distances;
}Trong hàm dijkstra, mình khởi tạo khoảng cách từ điểm xuất phát đến tất cả các đỉnh là vô cùng lớn, ngoại trừ điểm xuất phát (0). Sau đó, sử dụng hàng đợi để chọn đỉnh có khoảng cách ngắn nhất, cập nhật khoảng cách cho các đỉnh lân cận, và tiếp tục lặp qua quá trình này cho đến khi tất cả các đỉnh đã được đánh dấu là thăm.
const distances = dijkstra(graph, 0);
console.log(distances); // Kết quả: { '0': 0, '1': 3, '2': 1, '3': 4 }Kết quả này cho thấy khoảng cách ngắn nhất từ đỉnh 0 đến các đỉnh còn lại trong đồ thị:
- Khoảng cách từ đỉnh 0 đến đỉnh 1 là 3.
- Khoảng cách từ đỉnh 0 đến đỉnh 2 là 1.
- Khoảng cách từ đỉnh 0 đến đỉnh 3 là 4.
4. Phân Tích Độ Phức Tạp Thuật Toán
Độ phức tạp của thuật toán Dijkstra phụ thuộc vào cách biểu diễn đồ thị và cách triển khai hàng đợi ưu tiên.
- Nếu sử dụng danh sách kề và hàng đợi là một heap, độ phức tạp là O(E log V), với E là số cạnh và V là số đỉnh.
- Nếu sử dụng ma trận kề và hàng đợi là một heap, độ phức tạp sẽ là O(V²).
Mình chọn cách sử dụng danh sách kề và hàng đợi đơn giản với mảng, độ phức tạp sẽ gần với O(V²).
5. Những Điểm Lưu Ý Khi Sử Dụng Thuật Toán Dijkstra
Thuật toán Dijkstra có một số điểm quan trọng cần lưu ý:
- Thuật toán Dijkstra chỉ hoạt động tốt khi trọng số của các cạnh là không âm. Nếu có trọng số âm, bạn nên sử dụng thuật toán khác như là Bellman-Ford.
- Dijkstra không nhất thiết tìm thấy đường đi ngắn nhất nếu đồ thị có chứa chu trình âm (negative cycle).
6. Kết Luận
Thuật toán Dijkstra là một thuật toán để tìm đường đi ngắn nhất trong đồ thị. Trong bài viết này, chúng ta đã tìm hiểu chi tiết về cách hoạt động của thuật toán này và triển khai nó bằng ngôn ngữ TypeScript. Hy vọng, qua bài viết này sẽ giúp bạn tiếp cận nhanh chóng hơn.
Các bài viết liên quan: