Quy Hoạch Động (Dynamic Programming) Bài toán đường đi ngắn nhất (Shortest Path Problem)
Thời gian đọc: 7 phút
Thời gian đọc: 7 phút
Bài toán đường đi ngắn nhất (Shortest Path Problem) là một trong những bài toán cơ bản và quan trọng trong lĩnh vực tối ưu hóa và lý thuyết đồ thị. Bài toán này yêu cầu tìm ra đường đi ngắn nhất từ một điểm xuất phát đến một điểm đích trong một mạng lưới các điểm và các cạnh có trọng số. Trong lập trình, việc giải quyết bài toán này có thể ứng dụng trong nhiều lĩnh vực như giao thông, mạng máy tính, logistics, và nhiều bài toán phức tạp khác. Trong bài viết này, chúng ta sẽ sử dụng PHP để giải quyết bài toán đường đi ngắn nhất thông qua thuật toán Dijkstra.
Trong một đồ thị có các điểm (node) và các cạnh (edge) kết nối giữa các điểm đó, mỗi cạnh có một trọng số nhất định (thể hiện khoảng cách hoặc chi phí). Bài toán đặt ra là từ một điểm bắt đầu (source node), tìm đường đi ngắn nhất đến một điểm kết thúc (destination node) sao cho tổng trọng số trên đường đi là nhỏ nhất.
Ví dụ:
Bài toán đường đi ngắn nhất có nhiều ứng dụng trong thực tế:
Thuật toán Dijkstra là một trong những thuật toán phổ biến nhất để giải bài toán đường đi ngắn nhất trên đồ thị có trọng số dương. Nguyên lý của thuật toán Dijkstra là lựa chọn đường đi ngắn nhất từ điểm khởi đầu và mở rộng ra các điểm lân cận cho đến khi tìm được đường đi ngắn nhất đến điểm đích.
Các bước cơ bản của thuật toán Dijkstra:
INF), riêng khoảng cách đến chính nó là 0.Dưới đây là cách triển khai thuật toán Dijkstra bằng PHP:
<?php
// Hàm Dijkstra để tìm đường đi ngắn nhất
function dijkstra($graph, $source) {
// Số lượng nút
$numNodes = count($graph);
// Khởi tạo khoảng cách từ source đến tất cả các nút là vô cùng
$dist = array_fill(0, $numNodes, PHP_INT_MAX);
$dist[$source] = 0;
// Khởi tạo mảng đã thăm
$visited = array_fill(0, $numNodes, false);
// Hàng đợi ưu tiên
$queue = new SplPriorityQueue();
// Đưa điểm bắt đầu vào hàng đợi với trọng số 0
$queue->insert($source, 0);
while (!$queue->isEmpty()) {
// Lấy điểm có khoảng cách nhỏ nhất
$minNode = $queue->extract();
// Nếu đã thăm thì bỏ qua
if ($visited[$minNode]) {
continue;
}
// Đánh dấu nút này đã được thăm
$visited[$minNode] = true;
// Duyệt qua các nút kề
foreach ($graph[$minNode] as $neighbor => $weight) {
if (!$visited[$neighbor]) {
// Tính toán khoảng cách mới
$newDist = $dist[$minNode] + $weight;
// Nếu khoảng cách này nhỏ hơn khoảng cách hiện tại, cập nhật lại
if ($newDist < $dist[$neighbor]) {
$dist[$neighbor] = $newDist;
$queue->insert($neighbor, -$newDist);
}
}
}
}
return $dist;
}
// Ví dụ về đồ thị với các cạnh có trọng số
$graph = [
0 => [1 => 10, 2 => 3],
1 => [2 => 1, 3 => 2],
2 => [1 => 4, 3 => 8, 4 => 2],
3 => [4 => 7],
4 => [3 => 9]
];
// Điểm bắt đầu
$source = 0;
// Gọi hàm Dijkstra để tìm đường đi ngắn nhất
$distances = dijkstra($graph, $source);
// Hiển thị khoảng cách từ điểm bắt đầu đến tất cả các điểm khác
echo "Khoảng cách ngắn nhất từ điểm $source: \n";
foreach ($distances as $node => $distance) {
echo "Đến điểm $node: $distance\n";
}
?>
$graph[0] = [1 => 10, 2 => 3] có nghĩa là từ điểm 0, có thể đi đến điểm 1 với trọng số 10 và đến điểm 2 với trọng số 3.dijkstra():
$dist lưu trữ khoảng cách ngắn nhất từ điểm bắt đầu đến tất cả các điểm khác.$visited đánh dấu các điểm đã được thăm.SplPriorityQueue) được sử dụng để chọn điểm có khoảng cách ngắn nhất.Ví dụ với đồ thị trên, khi chạy đoạn mã PHP, kết quả sẽ là:
Khoảng cách ngắn nhất từ điểm 0:
Đến điểm 0: 0
Đến điểm 1: 7
Đến điểm 2: 3
Đến điểm 3: 9
Đến điểm 4: 5
Bài toán đường đi ngắn nhất là một vấn đề cơ bản nhưng vô cùng quan trọng trong lĩnh vực tối ưu hóa và lý thuyết đồ thị. Thông qua việc triển khai bằng PHP và áp dụng thuật toán Dijkstra, chúng ta đã có thể tìm ra đường đi ngắn nhất một cách hiệu quả. Hiểu rõ về bài toán này không chỉ giúp bạn giải quyết các vấn đề liên quan đến điều hướng, giao thông, mạng máy tính mà còn mở ra nhiều cơ hội áp dụng trong các lĩnh vực khác nhau.
