🔍 Giải Bài Toán Đường Đi Ngắn Nhất (Shortest Path Problem) Bằng Thuật Toán Dijkstra Trong PHP

1. Mô tả Bài Toán

Bài toán đường đi ngắn nhất 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 yêu cầu tìm đường đi có tổng trọng số nhỏ nhất từ một điểm xuất phát đến một điểm đích trong một đồ thị có hướng hoặc vô hướng, với các cạnh mang trọng số dương.

Ví dụ:

Giả sử bạn có một mạng lưới các thành phố kết nối với nhau bằng các tuyến đường, mỗi tuyến đường có độ dài cụ thể. Yêu cầu là tìm tuyến đường ngắn nhất từ thành phố A đến thành phố B.

2. Ứng Dụng Thực Tế

Bài toán này có nhiều ứng dụng thực tế trong các lĩnh vực:

• 🛰️ Định vị GPS: Tìm đường đi nhanh nhất giữa hai địa điểm.
• 🌐 Mạng máy tính: Tối ưu hóa truyền dữ liệu giữa các server.
• 🚚 Logistics: Lên kế hoạch vận chuyển hàng hóa hiệu quả nhất.
• 🔄 Tối ưu hóa nguồn lực: Giảm chi phí phân phối, sản xuất.

3. Thuật Toán Dijkstra

Dijkstra là một thuật toán nổi tiếng được dùng để giải bài toán đường đi ngắn nhất trên đồ thị không có trọng số âm.

Các bước của thuật toán:

1. Khởi tạo mảng distance[] với giá trị vô cực (INF) cho tất cả các điểm, trừ điểm xuất phát là 0.
2. Dùng một hàng đợi ưu tiên (hoặc mảng đơn giản) để chọn điểm có khoảng cách nhỏ nhất chưa xét.
3. Cập nhật khoảng cách ngắn nhất cho các điểm kề nếu tìm được đường đi ngắn hơn.
4. Lặp lại đến khi duyệt hết tất cả các điểm hoặc tìm được đường đi đến đích.

4. Cài Đặt Bằng PHP

⚙️ Dữ liệu mẫu: đồ thị có hướng dưới dạng danh sách kề

$graph = [
    'A' => ['B' => 1, 'C' => 4],
    'B' => ['C' => 2, 'D' => 5],
    'C' => ['D' => 1],
    'D' => []
];

🧠 Hàm thuật toán Dijkstra:

function dijkstra($graph, $start, $end) {
    $dist = [];
    $prev = [];
    $queue = [];

    foreach ($graph as $node => $edges) {
        $dist[$node] = INF;
        $prev[$node] = null;
        $queue[$node] = true;
    }

    $dist[$start] = 0;

    while (!empty($queue)) {
        // Tìm node có khoảng cách nhỏ nhất
        $minDist = INF;
        $minNode = null;

        foreach ($queue as $node => $_) {
            if ($dist[$node] < $minDist) {
                $minDist = $dist[$node];
                $minNode = $node;
            }
        }

        if ($minNode === null) break; // Không còn đường đi
        if ($minNode === $end) break; // Đã đến đích

        foreach ($graph[$minNode] as $neighbor => $weight) {
            $alt = $dist[$minNode] + $weight;
            if ($alt < $dist[$neighbor]) {
                $dist[$neighbor] = $alt;
                $prev[$neighbor] = $minNode;
            }
        }

        unset($queue[$minNode]); // Đã xét xong
    }

    // Truy vết lại đường đi
    $path = [];
    for ($node = $end; $node !== null; $node = $prev[$node]) {
        array_unshift($path, $node);
    }

    return [
        'distance' => $dist[$end],
        'path' => $path
    ];
}

🧪 Kết quả thử nghiệm:

$result = dijkstra($graph, 'A', 'D');

echo "Khoảng cách ngắn nhất: " . $result['distance'] . "n";
echo "Đường đi: " . implode(" → ", $result['path']);

Output:

Khoảng cách ngắn nhất: 4
Đường đi: A → B → C → D

5. Tối Ưu & Mở Rộng

• Tối ưu hiệu năng: Có thể dùng hàng đợi ưu tiên kiểu Min-Heap (như thư viện SPL PriorityQueue).
• Mở rộng bài toán:
  • Nếu đồ thị có cạnh âm: sử dụng Bellman-Ford.
  • Nếu cần tính tất cả các cặp đường đi: dùng Floyd-Warshall.
  • Nếu cần tính trên bản đồ thực: kết hợp với dữ liệu thực tế từ Google Maps API hoặc OpenStreetMap.

6. Kết Luận

Bài toán đường đi ngắn nhất là một trong những bài toán nền tảng trong lập trình và ứng dụng rộng rãi trong đời sống, từ định vị GPS cho đến tối ưu hóa mạng và chuỗi cung ứng. Với PHP và thuật toán Dijkstra, chúng ta có thể dễ dàng mô phỏng, thử nghiệm và áp dụng thuật toán này để giải các bài toán thực tế.

• Algorithm
• Dijkstra
• Dynamic Programming