đặt vấn đề tìm đường đi cơ bản (đường đi không có đỉnh lặp lại) ngắn nhất. Vấn đề đó là một vấn đề hết sức phức tạp mà ta sẽ không bàn tới ở đây. Dưới đây, chúng tôi giới thiệu hai thuật toán giải bài toán này là thuật toán Ford – Bellman và thuật toán Dijkstra. Giới thiệu thuật toán Ford - Bellman Thuật toán Ford-Bellman có thể phát biểu rất đơn giản: Với đỉnh xuất phát S.
Gọi d(v) là khoảng cách từ S tới v. Ban đầu d(S) được khởi gán bằng 0 còn các d(v) với v S được khởi gán bằng +. Sau đó ta tối ưu hoá dần các d(v) như sau: Xét mọi cặp đỉnh u, v của đồ thị, nếu có một cặp đỉnh u, v mà d(v) > d(u) + c(u, v) thì ta đặt lại d(v) := d(u) + c(u, v). Tức là nếu độ dài đường đi từ S tới v lại lớn hơn tổng độ dài đường đi từ S tới u cộng với chi phí đi từ u tới v thì ta sẽ huỷ bỏ đường đi từ S tới v đang có và coi đường đi từ S tới v chính là đường đi từ S tới u sau đó đi tiếp từ u tới v.
Chú ý rằng ta đặt c[u, v] = + nếu (u, v) không là cung. Thuật toán sẽ kết thúc khi không thể tối ưu thêm bất kỳ một nhãn d[v] nào nữa. Tính dừng của thuật toán: Tại bước lặp 0: Bước khởi tạo d(S) = 0; d(v) := + với v S: thì dãy d(v) chính là độ dài đường đi ngắn nhất từ S tới v đi qua không quá 0 cạnh Trang 23 z Giả sử tại bước lặp thứ i, d(v) bằng độ dài đường đi ngắn nhất từ S tới v qua không quá i cạnh, thì do tính chất: đường đi từ S tới v qua không quá i + 1 cạnh sẽ phải thành lập bằng cách: lấy một đường đi từ S tới một đỉnh u nào đó qua không quá i cạnh, rồi đi tiếp tới v bằng cung (u, v). Nên độ dài đường đi ngắn nhất từ S tới v qua không quá i + 1 cạnh sẽ được tính bằng giá trị nhỏ nhất trong các giá trị: (Nguyên lý tối ưu Bellman) Độ dài đường đi ngắn nhất từ S tới v qua không quá i cạnh Độ dài đường đi ngắn nhất từ S tới u qua không quá i cạnh cộng với trọng số cạnh (u, v) (u) Nên sau bước lặp tối ưu các d(v) bằng công thức d(v) bước i+1 = min(d(v)bước i, d(u)bước i+ c(u, v)) thì các d(v) sẽ bằng độ dài đường đi ngắn nhất từ S tới v qua không quá i + 1 cạnh.
Sau bước lặp tối ưu thứ n - 1, ta có d(v) = độ dài đường đi ngắn nhất từ S tới v qua không quá n - 1 cạnh. Vì đồ thị không có chu trình âm nên sẽ có một đường đi ngắn nhất từ S tới v là đường đi cơ bản (qua không quá n - 1 cạnh). Tức là d(v) sẽ là độ dài đường đi ngắn nhất từ S tới v. Vậy thì số bƣớc lặp tối ƣu hoá sẽ không quá n - 1 bƣớc.
Nếu mỗi bước ta mô tả dưới dạng: for u := 1 to n do for v := 1 to n do d(v) := min(d(v), d(u) + c(u, v)); Thì do sự tối ưu bắc cầu (dùng d(u) tối ưu d(v) rồi lại có thể dùng d(v) tối ưu d(w) nữa.) nên chỉ làm tốc độ tối ưu nhãn d(v) tăng nhanh lên chứ không thể giảm đi được. Giới thiệu thuật toán thuật toán Dijkstra Thuật toán Dijkstra (E.Dijkstra - 1959) có thể mô tả như sau: Trang 24 z Bước 1: Khởi tạo Với đỉnh v V, gọi nhãn d[v] là độ dài đường đi ngắn nhất từ s tới v. Ta sẽ tính các d[v]. Nhãn của mỗi đỉnh có hai trạng thái tự do hay cố định, nhãn tự do có nghĩa là có thể còn tối ưu hơn được nữa và nhãn cố định tức là d[v] đã bằng độ dài đường đi ngắn nhất từ s tới v nên không thể tối ưu thêm.
Để làm điều này ta có thể sử dụng kỹ thuật đánh dấu: Free[v] = TRUE hay FALSE tuỳ theo d[v] tự do hay cố định. Ban đầu các nhãn đều tự do. Bước 2: Lặp Cố định nhãn: Chọn trong các đỉnh có nhãn tự do, lấy ra đỉnh u là đỉnh có d[u] nhỏ nhất, và cố định nhãn đỉnh u. Sửa nhãn: Dùng đỉnh u, xét tất cả những đỉnh v và sửa lại các d[v] theo công thức: d[v] := min(d[v], d[u] + c[u, v]) Bước lặp sẽ kết thúc khi mà đỉnh đích t được cố định nhãn (tìm được đường đi ngắn nhất từ s đến t); hoặc tại thao tác cố định nhãn, tất cả các đỉnh tự do đều có nhãn là + (không tồn tại đường đi).
Có thể đặt câu hỏi, ở thao tác 1, tại sao đỉnh u như vậy được cố định nhãn, giả sử d[u] còn có thể tối ưu thêm được nữa thì tất phải có một đỉnh t mang nhãn tự do sao cho d[u] > d[t] + c[t, u]. Do trọng số c[t, u] không âm nên d[u] > d[t], trái với cách chọn d[u] là nhỏ nhất. Tất nhiên trong lần lặp đầu tiên thì S là đỉnh được cố định nhãn do d[s] = 0. Bước 3: Kết hợp với việc lưu vết đường đi trên từng bước sửa nhãn, thông báo đường đi ngắn nhất tìm được hoặc cho biết không tồn tại đường đi (d[t] = +).
Có thể mô tả ngắn gọn thuật toán bằng giả mã như sau: Bước 1: d[s] = 0 ; d[v] = + (v V\{s}); u = s; Trang 25 z Bước 2: Lặp nếu u t (với u S) 2.2 Chọn v có d[v] nhỏ nhất //v=0 không có đường 2.3 Nếu v 0 thì thêm v vào S; u = v Bước 3: In ra đường đi tối ưu từ s đến t hoặc thông báo vô nghiệm. Độ phức tạp Nếu đồ thị có nhiều đỉnh, ít cạnh, ta có thể sử dụng danh sách kề kèm trọng số để biểu diễn đồ thị, tuy nhiên tốc độ của thuật toán Dijkstra vẫn khá chậm vì trong trường hợp xấu nhất, nó cần n lần cố định nhãn và mỗi lần tìm đỉnh để cố định nhãn sẽ mất một đoạn chương trình với độ phức tạp O(n). Vậy độ phức tạp của thuật toán Dijkstra là O(n2). Để tăng tốc độ, người ta thường sử dụng cấu trúc dữ liệu Heap để lưu các đỉnh chưa cố định nhãn.
Heap ở đây là một cây nhị phân hoàn chỉnh thoả mãn: Nếu u là đỉnh lưu ở nút cha và v là đỉnh lưu ở nút con thì d[u] d[v] (Đỉnh r lưu ở gốc Heap là đỉnh có d[r] nhỏ nhất). Các thuật toán tìm kiếm trên cây khung 6. Bài toán cây khung Khái niệm cây khung: Cho đồ thị G = (V, E) vô hướng, liên thông và T = (V,E’) là một đồ thị con của G (E’ E). Khi đó, T được gọi là cây khung (cây bao trùm) nếu T liên thông và không có chu trình đơn Cho G = (V, E, w) là đồ thị vô hướng liên thông có trọng số, với một cây khung T của G, ta gọi trọng số của cây T là tổng trọng số các cạnh trong T.
Yêu cầu: Trong số các cây khung của G, chỉ ra cây khung có trọng số nhỏ nhất. Trang 26 z Cây khung như vậy được gọi là cây khung nhỏ nhất của đồ thị, và bài toán đó gọi là bài toán xây dựng cây khung nhỏ nhất. Dưới đây ta sẽ xét một trong hai thuật toán thông dụng để giải bài toán cây khung nhỏ nhất của đơn đồ thị vô hướng có trọng số. Giới thiệu thuật toán Prim Một trong hai thuật toán quan trọng để giải bài toán tìm cây khung nhỏ nhất là thuật toán Prim.
Thuật toán đó có thể phát biểu hình thức như sau: Đơn đồ thị vô hướng G = (V, E,w). Xét cây T trong G và một đỉnh v, gọi khoảng cách từ v tới T là trọng số nhỏ nhất trong số các cạnh nối v với một đỉnh nào đó trong T: d[v] = min{w[u, v] uT} Ban đầu khởi tạo cây T chỉ gồm có mỗi đỉnh {1}. Sau đó cứ chọn trong số các đỉnh ngoài T ra một đỉnh gần T nhất, kết nạp đỉnh đó vào T đồng thời kết nạp luôn cả cạnh tạo ra khoảng cách gần nhất đó. Cứ làm như vậy cho tới khi: Hoặc đã kết nạp được tất cả n đỉnh thì ta có T là cây khung nhỏ nhất Hoặc chưa kết nạp được hết n đỉnh nhưng mọi đỉnh ngoài T đều có khoảng cách tới T là +.
Khi đó đồ thị đã cho không liên thông, ta thông báo việc tìm cây khung thất bại. Về mặt kỹ thuật cài đặt, ta có thể làm như sau: Sử dụng mảng đánh dấu Free. Free[v] = TRUE nếu như đỉnh v chưa bị kết nạp vào T. Gọi d[v] là khoảng cách từ v tới T.
Ban đầu khởi tạo d[1] = 0 còn d[2] = d[3] =. Tại mỗi bước chọn đỉnh đưa vào T, ta sẽ chọn đỉnh u nào ngoài T và có d[u] nhỏ nhất. Khi kết nạp u vào T rồi thì rõ ràng các nhãn d[v] sẽ thay đổi: d[v]mới := min(d[v]cũ, v[u, v]). Vấn đề chỉ có vậy (chương trình rất giống thuật toán Dijkstra, chỉ khác ở công thức tối ưu nhãn).
Trang 27 z Có thể mô tả thuật toán Prim bằng đoạn giả mã sau: Bước 1: Khởi tạo: T = {s} d[s] = 0, u = s (s - đỉnh xuất phát) d[v]=+∞(v ∉ T) Bước 2: Lặp N-1 lần (N số đỉnh của đồ thị): 2.1 Cập nhật các đỉnh kề với u ở ngoài T Nếu d[v] > w[u,v] trace[v] = u, d[v] = w[u,v] 2.2 Chọn v (v ∉ T) mà d[v] nhỏ nhất Nếu d[v] = +∞ đến bước 3 2.3 Kết nạp v vào T, u = v Bước 3: In ra cây khung hoặc thông báo vô nghiệm. Giới thiệu thuật toán Kruskal Thuật toán Kruskal dựa trên mô hình xây dựng cây khung bằng thuật toán hợp nhất [xxx], chỉ có điều thuật toán không phải xét các cạnh với thứ tự tuỳ ý mà xét các cạnh theo thứ tự đã sắp xếp: Với đồ thị vô hướng G = (V, E) có n đỉnh. Khởi tạo cây T ban đầu không có cạnh nào. Xét tất cả các cạnh của đồ thị từ cạnh có trọng số nhỏ đến cạnh có trọng số lớn, nếu việc thêm cạnh đó vào T không tạo thành chu trình đơn trong T thì kết nạp thêm cạnh đó vào T.