Algorithms & Applications
Trang chủ / Module 10
🗺️ Module 10 / 14 · 1-2 tuần

Đồ thị nâng cao: Shortest Path & Minimum Spanning Tree

Dijkstra cho đường đi ngắn nhất có trọng số, giới thiệu Bellman-Ford, và Minimum Spanning Tree — ứng dụng cho routing mạng và thiết kế network topology.

DijkstraMST
📌 Vì sao module này quan trọng

Khi cạnh đồ thị có "chi phí" khác nhau (thời gian, khoảng cách, độ trễ mạng), BFS (Module 9) không còn đủ. Dijkstra là thuật toán đứng sau hầu hết hệ thống định tuyến (routing) thực tế — từ GPS đến giao thức mạng máy tính — kết hợp trực tiếp Heap đã học ở Module 5.

🎯 Mục tiêu học tập

  • Triển khai Dijkstra để tìm đường đi ngắn nhất trên đồ thị có trọng số không âm
  • Hiểu khi nào cần Bellman-Ford thay vì Dijkstra (đồ thị có trọng số âm)
  • Hiểu Minimum Spanning Tree và ứng dụng trong thiết kế network topology
  • Nhận diện được các bài toán thực tế ánh xạ đúng vào Shortest Path hoặc MST

Dijkstra — Đường đi ngắn nhất kết hợp Heap

import heapq

def dijkstra(graph: dict, start: str) -> dict:
    # graph[node] = [(neighbor, weight), ...]
    distances = {node: float("inf") for node in graph}
    distances[start] = 0
    pq = [(0, start)]              # Priority Queue (Module 5) — luôn xử lý node gần nhất trước
    while pq:
        dist, node = heapq.heappop(pq)
        if dist > distances[node]:
            continue                # đã tìm được đường ngắn hơn trước đó, bỏ qua
        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))
    return distances

Dijkstra là ứng dụng trực tiếp và đẹp nhất của Priority Queue (Module 5): luôn xử lý node có khoảng cách tạm thời nhỏ nhất tiếp theo (giống extract-min liên tục), cập nhật khoảng cách các node lân cận nếu tìm được đường ngắn hơn (relaxation). Độ phức tạp O((V + E) log V) nhờ Heap — đây chính là lý do Module 5 được học trước module này.

⚠️ Giới hạn quan trọng

Dijkstra chỉ đúng với trọng số không âm — với đồ thị có trọng số âm (hiếm trong bài toán khoảng cách vật lý, nhưng phổ biến trong bài toán tài chính/mô hình hoá chi phí có "lợi ích"), cần dùng Bellman-Ford (chậm hơn — O(V×E), nhưng xử lý đúng trọng số âm và phát hiện được chu trình âm).

Ứng dụng thực tế của Shortest Path

  • Định tuyến mạng máy tính: giao thức định tuyến (routing protocol) tìm đường đi có độ trễ/chi phí thấp nhất giữa các router.
  • GPS/Bản đồ: tìm đường đi ngắn nhất/nhanh nhất giữa 2 địa điểm (thực tế dùng các biến thể tối ưu hơn như A* — mở rộng Dijkstra với heuristic).
  • Load Balancing thông minh: chọn server "gần nhất" (theo độ trễ đo được) để định tuyến request — liên hệ trực tiếp Load Balancing đã học ở khoá Architecture Module 7.

Minimum Spanning Tree — thiết kế Network Topology tiết kiệm nhất

Minimum Spanning Tree (MST) tìm tập cạnh nhỏ nhất (tổng trọng số thấp nhất) để kết nối tất cả node trong đồ thị thành 1 cây (không có chu trình, mọi node đều liên thông). Khác Shortest Path (tìm đường ngắn nhất giữa 2 điểm cụ thể), MST tối ưu cho việc kết nối toàn bộ hệ thống với chi phí thấp nhất — 2 thuật toán phổ biến: Kruskal (sắp xếp cạnh theo trọng số tăng dần, thêm cạnh nếu không tạo chu trình — dùng cấu trúc Union-Find) và Prim (tương tự Dijkstra, mở rộng cây từ 1 node, luôn thêm cạnh rẻ nhất nối ra ngoài cây hiện có — cũng dùng Heap).

Ứng dụng thực tế: thiết kế mạng cáp quang/điện kết nối nhiều địa điểm với chi phí lắp đặt thấp nhất, thiết kế network topology tối thiểu vẫn đảm bảo mọi service liên thông được với nhau (liên hệ Network Topology đã học ở khoá DevOps Module 9 và Docker Module 4, ở góc độ tối ưu chi phí thay vì chỉ đúng chức năng).

🏋️ Bài tập thực hành

Định tuyến trong mạng giả lập

Mô hình hoá 1 mạng gồm 8 "node" (máy chủ) với "cạnh" là độ trễ kết nối giữa chúng (số ngẫu nhiên). Triển khai Dijkstra để tìm đường đi có độ trễ thấp nhất từ 1 node bất kỳ đến tất cả node còn lại. Triển khai Kruskal hoặc Prim để tìm MST — chi phí lắp đặt tối thiểu để toàn bộ 8 node liên thông. So sánh và giải thích vì sao kết quả Shortest Path và MST khác nhau dù dùng cùng 1 đồ thị.

📚 Tài nguyên học tập

✅ Tự đánh giá hoàn thành

  • Triển khai đúng Dijkstra kết hợp Priority Queue
  • Giải thích được vì sao Dijkstra sai với trọng số âm, và khi nào cần Bellman-Ford
  • Phân biệt được bài toán Shortest Path và Minimum Spanning Tree
  • Ánh xạ đúng 1 bài toán thực tế vào Shortest Path hoặc MST