Bài 1: Google Maps tìm đường nhanh nhất thế nào? Thuật toán Dijkstra và A* trong đời sống

Mỗi ngày, hàng trăm triệu người mở Google Maps, Grab hay Be và chỉ mất chưa đến một giây để có lộ trình nhanh nhất. Đằng sau nút "Chỉ đường" là một trong những thuật toán nổi tiếng nhất mà học sinh chuyên Tin nào cũng học: Dijkstra – được nghĩ ra trong 20 phút bên tách cà phê năm 1956.

Bài mở đầu chuyên mục "Thuật toán trong đời sống". Mỗi bài sẽ lấy một ứng dụng bạn dùng hằng ngày, "mổ xẻ" xem bên trong là thuật toán gì, kèm code C++/Python chạy được để bạn tự thử.

1. Từ bản đồ đến đồ thị

Với máy tính, bản đồ không phải là hình ảnh mà là một đồ thị (graph):

• Đỉnh là các giao lộ, ngã ba, ngã tư.
• Cạnh là các đoạn đường nối giữa chúng. Đường một chiều là cạnh có hướng.
• Trọng số của cạnh là thời gian đi qua đoạn đường đó – phụ thuộc chiều dài, tốc độ cho phép, và cả tình trạng kẹt xe lúc đó.

Câu hỏi "đi từ nhà đến trường nhanh nhất thế nào?" trở thành bài toán kinh điển: tìm đường đi ngắn nhất trên đồ thị có trọng số không âm.

Bản đồ thu nhỏ: 6 giao lộ, số trên cạnh là thời gian (phút). Đường vàng là lộ trình nhanh nhất 1 → 3 → 6 → 5, tổng 20 phút.

2. Dijkstra: 20 phút bên tách cà phê

Năm 1956, nhà khoa học máy tính Hà Lan Edsger W. Dijkstra đi mua sắm ở Amsterdam cùng vị hôn thê. Trong cuộc phỏng vấn năm 2001 (đăng trên tạp chí Communications of the ACM), ông kể khi mệt, hai người ngồi xuống uống cà phê ở một quán ven đường, và ông nghĩ ra thuật toán tìm đường ngắn nhất "trong khoảng 20 phút", hoàn toàn không cần giấy bút. Thuật toán được công bố ba năm sau, vào năm 1959.

Ý tưởng

Dijkstra giống như một "vết dầu loang" lan ra từ điểm xuất phát:

1. Gán khoảng cách đến điểm xuất phát là 0, các điểm khác là vô cùng.
2. Mỗi bước, lấy ra đỉnh chưa chốt có khoảng cách nhỏ nhất – khoảng cách của nó chắc chắn đã tối ưu (vì mọi trọng số đều không âm).
3. Từ đỉnh đó, thử đi tiếp sang các đỉnh kề: nếu đi qua đỉnh này nhanh hơn, cập nhật lại khoảng cách (gọi là "nới lỏng" cạnh).
4. Lặp lại đến khi chốt được đích.

Để lấy nhanh đỉnh có khoảng cách nhỏ nhất, ta dùng hàng đợi ưu tiên (heap). Độ phức tạp khi đó là O((V + E) log V) – đủ nhanh cho hàng triệu đỉnh.

Code: tìm đường từ nhà đến trường

Chương trình dưới đây nhận bản đồ, in ra thời gian nhanh nhất và lộ trình cụ thể (truy vết bằng mảng trace):

Code C++ và Python

#include <bits/stdc++.h>
using namespace std;
// Bản đồ: n giao lộ, m đoạn đường một chiều (u -> v mất w phút)
int main(){
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    vector<vector<pair<int,long long>>> g(n + 1);
    for(int i = 0; i < m; i++){
        int u, v; long long w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }
    const long long INF = LLONG_MAX;
    vector<long long> dist(n + 1, INF);
    vector<int> trace(n + 1, -1);
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
    dist[s] = 0; pq.push({0, s});
    while(!pq.empty()){
        auto [d, u] = pq.top(); pq.pop();
        if(d != dist[u]) continue;          // bản ghi cũ, bỏ qua
        if(u == t) break;                   // đã chốt đích -> dừng sớm
        for(auto [v, w] : g[u])
            if(dist[u] + w < dist[v]){
                dist[v] = dist[u] + w;
                trace[v] = u;
                pq.push({dist[v], v});
            }
    }
    if(dist[t] == INF){ cout << "Khong co duong\n"; return 0; }
    vector<int> path;
    for(int v = t; v != -1; v = trace[v]) path.push_back(v);
    reverse(path.begin(), path.end());
    cout << "Thoi gian: " << dist[t] << " phut\nLo trinh:";
    for(int v : path) cout << ' ' << v;
    cout << '\n';
}

import heapq

def dijkstra(g, s, t):
    dist = {s: 0}
    trace = {s: None}
    pq = [(0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if d != dist[u]:
            continue
        if u == t:
            break
        for v, w in g.get(u, []):
            if v not in dist or d + w < dist[v]:
                dist[v] = d + w
                trace[v] = u
                heapq.heappush(pq, (dist[v], v))
    if t not in dist:
        return None, []
    path, v = [], t
    while v is not None:
        path.append(v)
        v = trace[v]
    return dist[t], path[::-1]

# Ví dụ: 1 = Nhà, 5 = Trường
g = {1: [(2, 7), (3, 9), (6, 14)], 2: [(3, 10), (4, 15)],
     3: [(4, 11), (6, 2)], 4: [(5, 6)], 6: [(5, 9)]}
print(dijkstra(g, 1, 5))   # (20, [1, 3, 6, 5])

Với bản đồ ví dụ ở hình trên (nhập 6 9 1 5 rồi 9 cạnh), chương trình in ra 20 phút, lộ trình 1 → 3 → 6 → 5. Để ý rằng đường "trông có vẻ thẳng" 1 → 6 → 5 lại mất 23 phút.

3. A*: tìm đường có định hướng

Dijkstra lan đều ra mọi phía – kể cả phía ngược với đích. Năm 1968, ba nhà nghiên cứu Peter Hart, Nils Nilsson và Bertram Raphael ở Viện nghiên cứu Stanford (SRI) công bố thuật toán A*, một phần trong dự án robot Shakey. Ý tưởng: ưu tiên đỉnh có

f(v) = g(v) + h(v), trong đó g(v) là thời gian đã đi từ điểm xuất phát đến v, còn h(v) là ước lượng thời gian còn lại từ v đến đích – ví dụ khoảng cách đường chim bay chia cho vận tốc tối đa.

Nếu h(v) không bao giờ ước lượng vượt quá thời gian thật (gọi là heuristic "chấp nhận được"), A* vẫn cho kết quả tối ưu nhưng thường phải xét ít đỉnh hơn Dijkstra rất nhiều, vì nó "biết" đích nằm ở hướng nào.

Phần thay đổi so với Dijkstra (C++)

// A*: giống Dijkstra nhưng ưu tiên theo f = g + h
// h(v) = khoảng cách đường chim bay từ v đến đích / vận tốc tối đa
// -> không bao giờ ước lượng quá thời gian thật, nên A* vẫn cho kết quả tối ưu
double h(int v){
    double dx = X[v] - X[t], dy = Y[v] - Y[t];
    return sqrt(dx*dx + dy*dy) / VMAX;
}
...
dist[s] = 0; pq.push({h(s), s});
while(!pq.empty()){
    auto [f, u] = pq.top(); pq.pop();
    if(f > dist[u] + h(u) + 1e-9) continue;
    if(u == t) break;
    for(auto [v, w] : g[u])
        if(dist[u] + w < dist[v]){
            dist[v] = dist[u] + w;
            pq.push({dist[v] + h(v), v});
        }
}

4. Thực tế: hàng tỷ người dùng, dưới 1 mili giây

Dijkstra và A* là nền móng, nhưng các bản đồ thực tế quá lớn để chạy "trần". Năm 2025, các trang tin công nghệ dẫn số liệu của Google cho biết Google Maps có hơn 2 tỷ người dùng mỗi tháng. Các hệ thống dẫn đường dùng thêm nhiều kỹ thuật tăng tốc:

• Contraction Hierarchies (2008): nhóm của Robert Geisberger (ĐH Karlsruhe, Đức) đề xuất tiền xử lý bản đồ: "co" dần các nút ít quan trọng và thêm các cạnh tắt (shortcut). Khi truy vấn, ta chỉ cần tìm kiếm hai chiều trên các nút "quan trọng hơn". Theo wiki OpenStreetMap, công cụ mã nguồn mở OSRM trả lời truy vấn trên cả bản đồ châu Âu thường dưới 1 mili giây.
• Multi-Level Dijkstra: chia bản đồ thành nhiều tầng vùng; OSRM khuyến nghị cách này khi cần cập nhật giao thông theo thời gian thực.
• Landmarks (ALT): GraphHopper dùng các "mốc" và bất đẳng thức tam giác để tạo heuristic tốt cho A*; năm 2017 họ báo cáo cách này giúp chế độ định tuyến linh hoạt nhanh hơn 15 lần.
• Dự đoán thời gian bằng AI: năm 2020, DeepMind công bố mạng nơ-ron đồ thị (Graph Neural Network) giúp Google Maps dự đoán thời gian di chuyển chính xác hơn tới 50% ở các thành phố như Jakarta, São Paulo, Tokyo. Nghĩa là AI dự đoán trọng số cạnh, còn thuật toán đồ thị vẫn là bộ khung tìm đường.

Chế độ xe máy ở Việt Nam

Tháng 7/2018, Google Maps ra mắt chế độ xe máy tại Việt Nam: lộ trình có thể đi qua ngõ hẻm nhỏ mà ô tô không vào được, tránh các tuyến cấm xe máy, và ước tính thời gian bằng mô hình học máy riêng cho tốc độ xe máy. Về mặt thuật toán, đó chính là một đồ thị khác: thêm cạnh (ngõ nhỏ), bỏ cạnh (đường cấm) và trọng số khác. Một khảo sát của HERE đăng trên VnExpress năm 2026 cho thấy 50% người đi xe máy ở Việt Nam thường xuyên dùng ứng dụng chỉ đường.

5. Bạn học được gì từ đây?

• Những bài đồ thị – đường đi ngắn nhất trong đề thi HSG không phải bài toán "trên giấy": nó đang chạy trong điện thoại của bạn mỗi ngày.
• Dijkstra chỉ đúng khi trọng số không âm. Nếu có cạnh âm, phải dùng Bellman-Ford.
• Trong thực tế, ý tưởng quan trọng không kém là tiền xử lý (như Contraction Hierarchies) – đổi thời gian chuẩn bị lấy tốc độ trả lời. Đây cũng là tư duy của mảng cộng dồn, sparse table mà bạn học ở chuyên đề nâng cao.

Bài tập luyện tập

• CSES – Shortest Routes I (Dijkstra cơ bản)
• CSES – Flight Discount (Dijkstra trên đồ thị trạng thái)
• CSES – Shortest Routes II (Floyd–Warshall)

Bạn có biết ứng dụng nào khác dùng thuật toán tìm đường? Gợi ý: game, robot hút bụi, định tuyến Internet… Hãy chia sẻ trong phần bình luận!

📖 ĐỌC TIẾP: THUẬT TOÁN TRONG ĐỜI SỐNG

Bài 2: Google xếp hạng hàng tỷ trang web thế nào? Thuật toán PageRank và chỉ mục ngược

Đọc tiếp: PageRank của Google →

← Bài trước: seam carving & QHĐXem tất cả 27 bài →

Nguồn tham khảo

• CACM – An Interview with Edsger W. Dijkstra (phỏng vấn năm 2001)
• Hart, Nilsson, Raphael (1968) – A Formal Basis for the Heuristic Determination of Minimum Cost Paths
• Wikipedia – A* search algorithm
• KIT – Contraction Hierarchies (Geisberger et al., 2008)
• OSRM – Running OSRM (CH và MLD)
• OpenStreetMap Wiki – OSRM
• GraphHopper – Flexible routing 15 times faster (2017)
• DeepMind – Traffic prediction with advanced Graph Neural Networks (2020)
• Trending Topics – Google Maps 20 năm (2025)
• Việt Nam News – Google Maps ra mắt chế độ xe máy tại Việt Nam (2018)
• VnExpress – 50% người đi xe máy ở Việt Nam dùng ứng dụng chỉ đường (2026)