Đặt vấn đề

Tưởng tượng bạn là một vị đại thần đang ngủ gục trên bàn làm việc. Bỗng chốc tỉnh dậy, bạn phát hiện mình đang ở trong cung điện nguy nga, có cung nữ hầu hạ, vàng bạc chạm khắc tinh xảo. Một thái giám vội vàng chạy đến báo: "Bệ hạ đã mất, điện hạ cần lập tức trở về Bắc Kinh để nối ngôi! Thêm nữa, Nhị hoàng tử cũng đã xuất phát từ Nam Kinh, âm mưu đoạt ngôi!" Bạn lập tức yêu cầu bản đồ hành trình. Việc sống còn giờ đây phụ thuộc vào việc tìm ra con đường nhanh nhất từ **Nam Kinh** đến **Bắc Kinh**. Vấn đề đặt ra: Trong một đồ thị liên kết các thành phố, hãy xác định đường đi ngắn nhất (theo số cạnh hoặc trọng số) từ điểm xuất phát đến điểm đích.

Phương pháp tiếp cận cơ bản: BFS cho đồ thị không trọng số

Nếu tất cả các cạnh đều có trọng số bằng nhau (ví dụ = 1), ta có thể dùng Tìm kiếm theo chiều rộng (BFS) để tìm đường đi ngắn nhất:

Nam Kinh → Trịnh Châu → Bắc Kinh        = 3 bước
Nam Kinh → Trịnh Châu → Thiên Tân → Bắc Kinh = 4 bước
Nam Kinh → Tế Nam → Thiên Tân → Bắc Kinh     = 4 bước

Rõ ràng, con đường tối ưu là Nam Kinh → Trịnh Châu → Bắc Kinh. Nhưng với đồ thị lớn và trọng số khác nhau, cần một giải thuật mạnh hơn — đó là Dijkstra.

Giải thuật Dijkstra – Tìm đường đi ngắn nhất có trọng số

Giải thuật Dijkstra là phương pháp nổi tiếng để tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác trong đồ thị có hướng hoặc vô hướng với trọng số không âm.

Nguyên lý hoạt động

• Khởi tạo khoảng cách từ đỉnh bắt đầu đến chính nó là 0, các đỉnh còn lại là ∞.
• Duy trì một tập hợp các đỉnh đã được xử lý (đã biết đường đi ngắn nhất).
• Sử dụng hàng đợi ưu tiên (min-heap) để luôn chọn đỉnh có khoảng cách tạm thời nhỏ nhất.
• Với mỗi đỉnh kề, kiểm tra xem đi qua đỉnh hiện tại có rút ngắn đường đến đỉnh kề hay không. Nếu có, cập nhật khoảng cách và cha của đỉnh kề.
• Lặp lại cho đến khi tất cả đỉnh đều được xử lý.

Các bước chi tiết

1. Chọn đỉnh nguồn (ví dụ: "Nam Kinh"), đặt dist["Nam Kinh"] = 0.
2. Thêm tất cả đỉnh chưa xử lý vào hàng đợi ưu tiên theo khoảng cách.
3. Lấy đỉnh có dist nhỏ nhất ra khỏi hàng đợi.
4. Cập nhật khoảng cách đến các đỉnh kề nếu tìm được đường ngắn hơn.
5. Thêm lại các đỉnh kề được cập nhật vào hàng đợi.
6. Lặp lại cho đến khi hàng đợi rỗng.

Cài đặt bằng Java

Dưới đây là mã nguồn minh họa giải thuật Dijkstra để tìm đường đi ngắn nhất giữa hai thành phố:

import java.util.*;

class CityGraph {
    private Map<String, List<Edge>> graph = new HashMap<>();

    // Thêm một thành phố vào đồ thị
    public void addCity(String city) {
        graph.putIfAbsent(city, new ArrayList<>());
    }

    // Thêm đường nối giữa hai thành phố với trọng số
    public void connectCities(String from, String to, int distance) {
        graph.get(from).add(new Edge(to, distance));
        graph.get(to).add(new Edge(from, distance)); // Đồ thị vô hướng
    }

    // Tìm đường đi ngắn nhất từ source đến destination
    public List<String> findShortestPath(String source, String destination) {
        Map<String, Integer> minDist = new HashMap<>();
        Map<String, String> previousNode = new HashMap<>();
        Set<String> visited = new HashSet<>();
        PriorityQueue<NodeEntry> pq = new PriorityQueue<>((a, b) -> a.distance - b.distance);

        // Khởi tạo khoảng cách ban đầu
        for (String city : graph.keySet()) {
            minDist.put(city, Integer.MAX_VALUE);
        }
        minDist.put(source, 0);
        pq.offer(new NodeEntry(source, 0));

        while (!pq.isEmpty()) {
            NodeEntry current = pq.poll();
            String node = current.city;

            if (visited.contains(node)) continue;
            visited.add(node);

            // Cập nhật khoảng cách tới các thành phố kề
            for (Edge edge : graph.get(node)) {
                if (visited.contains(edge.target)) continue;

                int newDist = minDist.get(node) + edge.weight;
                if (newDist < minDist.get(edge.target)) {
                    minDist.put(edge.target, newDist);
                    previousNode.put(edge.target, node);
                    pq.offer(new NodeEntry(edge.target, newDist));
                }
            }
        }

        // Xây dựng đường đi từ đích về nguồn
        return buildPath(previousNode, source, destination);
    }

    private List<String> buildPath(Map<String, String> prev, String start, String end) {
        List<String> path = new ArrayList<>();
        String current = end;

        while (current != null && !current.equals(start)) {
            path.add(0, current);
            current = prev.get(current);
        }
        path.add(0, start);
        return path;
    }

    // Lớp mô tả cạnh nối giữa hai thành phố
    private static class Edge {
        String target;
        int weight;
        Edge(String t, int w) { target = t; weight = w; }
    }

    // Lớp dùng để đưa vào hàng đợi ưu tiên
    private static class NodeEntry {
        String city;
        int distance;
        NodeEntry(String c, int d) { city = c; distance = d; }
    }
}

Sử dụng chương trình

public static void main(String[] args) {
    CityGraph map = new CityGraph();
    map.addCity("Bắc Kinh");
    map.addCity("Thiên Tân");
    map.addCity("Tế Nam");
    map.addCity("Nam Kinh");
    map.addCity("Trịnh Châu");

    map.connectCities("Bắc Kinh", "Thiên Tân", 1);
    map.connectCities("Bắc Kinh", "Trịnh Châu", 1);
    map.connectCities("Thiên Tân", "Tế Nam", 1);
    map.connectCities("Tế Nam", "Nam Kinh", 1);
    map.connectCities("Nam Kinh", "Trịnh Châu", 1);

    List<String> route = map.findShortestPath("Nam Kinh", "Bắc Kinh");
    System.out.println("Tuyến đường ngắn nhất: " + route);
}

Kết quả:
Tuyến đường ngắn nhất: [Nam Kinh, Trịnh Châu, Bắc Kinh]