Lý thuyết đồ thị¶
Phần này mình sử dụng các quyển sách dành cho học sinh chuyên Tin [14].
Đường đi ngắn nhất¶
Đồ thị có trọng số là bộ ba \(G = (V, E, w)\), trong đó \(G = (V, E)\) là đồ thị và \(w\) là hàm trọng số:
Hàm trọng số gán cho mỗi cạnh \(e\) của đồ thị một số thực \(w(e)\), gọi là trọng số (weight) của cạnh.
Nếu cạnh \(e = (u, v)\) thì ta cũng kí hiệu \(w(u, v) = w(e)\).
Đối với đồ thị \(n\) đỉnh, ta có thể biểu diễn bằng ma trận trọng số \(W = \{ w_{uv} \}_{n \times n}\), trong đó \(w_{uv}\) là trọng số của cạnh \((u, v)\).
Khi \((u, v) \notin E\) thì \(w_{uv}\) sẽ được gán giá trị đặc biệt để nhận biết đây không phải là cạnh, ví dụ là \(-\infty\), \(+\infty\), \(0\).
Đường đi, chu trình được định nghĩa giống trường hợp không có trọng số, chỉ khác là độ dài đường đi không tính bằng số cạnh đi qua mà là tổng trọng số của các cạnh đi qua. Độ dài của đường đi \(P\) được kí hiệu là \(w(P)\).
Đường đi ngắn nhất xuất phát từ một đỉnh¶
(Single-source shortest path)
Cho đồ thị có trọng số \(G = (V, E, w)\). Hãy tìm các đường đi ngắn nhất xuất phát từ đỉnh \(s \in V\) đến tất cả đỉnh còn lại của đồ thị.
Độ dài của đường đi từ \(s\) tới \(t\), kí hiệu là \(\delta(s, t)\), gọi là khoảng cách (distance) từ \(s\) tới \(t\).
Nếu không tồn tại đường đi từ \(s\) tới \(t\) thì ta đặt \(\delta(s, t) = +\infty\).
Cấu trúc bài toán con tối ưu¶
Định lí 1-1. Cho đồ thị có trọng số \(G = (V, E, w)\). Gọi \(P = (v_1, v_2, \ldots, v_k)\) là đường đi ngắn nhất từ \(v_1\) tới \(v_k\). Khi đó với mọi \(i\), \(j\) sao cho \(1 \leqslant i \leqslant j \leqslant k\), đường đi \(P_{ij} = (v_i, v_{i+1}, \ldots, v_j)\) là đường đi ngắn nhất từ \(v_i\) tới \(v_j\).
Từ định lí 1-1 ta có thể thấy các thuật toán tìm đường đi ngắn nhất đều là thuật toán quy hoạch động hoặc tham lam (Floyd, Dijkstra).
Lưu ý, khi đồ thị có chu trình âm thì bài toán tìm đường đi ngắn nhất là bài toán NP đầy đủ.
Bài toán đo khoảng cách¶
Nếu đồ thị không có chu trình âm thì có thể chứng minh rằng một trong những đường đi ngắn nhất là đường đi đơn.
Khi đó, chỉ cần biết khoảng cách từ \(s\) tới tất cả đỉnh khác thì đường đi ngắn nhất từ \(s\) tới \(t\) có thể tìm qua thuật toán sau.
Trước tiên, ta tìm đỉnh \(v_1 \neq t\) sao cho \(\delta(s, t) = \delta(s, v_1) + c(v_1, t)\).
Dễ thấy rằng luôn tồn tại đỉnh \(v_1\) như vậy, và đỉnh đó đứng liền trước \(t\) trên đuòng đi từ \(s\) tới \(t\).
Nếu \(v_1 = s\) thì đường đi ngắn nhất là đường đi trực tiếp theo cung \((s, t)\).
Nếu không thì vấn đề trở thành tìm đường đi ngắn nhất từ \(s\) tới \(v_1\). Tương tự, ta tìm được đỉnh \(v_2 \notin \{ t, v_1 \}\) sao cho
Tiếp tục tới khi ta có \(v_k = s\).
Nhãn và phép co¶
Với mỗi đỉnh \(v \in V\), nhãn khoảng cách \(d[v]\) là độ dài của đường đi nào đó từ \(s\) tới \(v\).
Nếu ta chưa xác định được đường đi nào từ \(s\) tới \(v\), gán nhãn \(d[v] = +\infty\).
Khi đó ta khởi tạo vói mọi \(v \in V\):
Do tính chất của nhãn khoảng cách, ta có \(d[v] \geqslant \delta(s, v)\) với mọi \(v \in V\).