Trong một directed graph (đồ thị có hướng, digraph), các cạnh có một hướng (A → B ≠ B → A). Trong một weighted graph (đồ thị có trọng số), mỗi cạnh mang một chi phí số (numeric cost) (khoảng cách, thời gian, dung lượng). Kết hợp cả hai mô hình hóa các hệ thống thực tế nơi quan hệ là một chiều và có một chi phí.
Biểu diễn
text
Weighted directed graph:
A --5--> B
A --2--> C
C --1--> B
Adjacency list với trọng số:
A: [(B,5), (C,2)]
B: []
C: [(B,1)]
python
graph = {
'A': [('B', 5), ('C', 2)], # cạnh có hướng, có trọng số
'B': [],
'C': [('B', 1)],
}
# Đường đi ngắn nhất A->B là A->C->B = 2 + 1 = 3, không phải cạnh trực tiếp 5.
Chúng mô hình hóa gì
| Lĩnh vực | Đỉnh | Cạnh có hướng, có trọng số |
|---|---|---|
| Bản đồ / GPS | nút giao | đường một chiều + thời gian di chuyển |
| Mạng | router | liên kết + độ trễ/băng thông |
| Lập lịch tác vụ | tác vụ | phụ thuộc + thời lượng |
| Tài chính | tiền tệ | tỷ giá hối đoái |
Các thuật toán then chốt
| Mục tiêu | Thuật toán | Độ phức tạp |
|---|---|---|
| Đường đi ngắn nhất (trọng số không âm) | Dijkstra | O((V+E) log V) |
| Đường đi ngắn nhất (cạnh âm) | Bellman-Ford | O(VE) |
| Sắp thứ tự với phụ thuộc | Topological sort | O(V+E) |
| Phát hiện chu trình / khả năng tới được | DFS | O(V+E) |
Tại sao điều này quan trọng
Hướng và trọng số là cái biến một graph trừu tượng thành một mô hình trung thực của các bài toán định tuyến, lập lịch, và phụ thuộc điều khiển các ứng dụng thực tế.
Lựa chọn thuật toán xoay quanh các thuộc tính này — ví dụ, trọng số âm loại trừ Dijkstra và đòi hỏi Bellman-Ford.