Thuật toán Johnson tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ
thị
Lưu Tuấn Anh
Thuật toán Johnson tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh với độ phức tạp là
O(V2LgV+VE). Với đồ thị thưa, nó tốt hơn là việc lặp đi lặp lại việc điều chỉnh các ma
trận hay thuật toán FLOYD-WARSHALL. Thuật toán cho kết quả trả về ma trận trọng số
đường đi ngắn nhất giữa tất cả các cặp đỉnh hay báo cáo về đồ thị nhập vào có chứa chu
trình âm (chu trình âm là 1 chu trình trong đồ thị có tổng trọng số các đỉnh thuộc chu trình
là 1 số âm, nếu trong đồ thị có chu trình âm, ta cứ đi trên chu trình ấy vô số lần thì ta sẽ có
ĐNN vô cùng bé ). Thuật toán Johnson sử dụng cả 2 chương trình con là thuật toán
Dijkstra và thuật toán Bellman –Ford (tôi không trình bày 2 thuật toán này nữa).
Thuật toán Johnson sử dụng kĩ thuật “Gán lại trọng số” (REWEIGHTING). Nếu tất cả các
trọng số W của các đỉnh trong 1 đồ thị G = (V,E) đều không âm (V là tập đỉnh của đồ thị,
E là tập cạnh của đồ thị, W là hàm trọng số trên mỗi đỉnh), ta có thể tìm đường đi ngắn
nhất giữa tất cả các cặp đỉnh bằng cách chạy thuật toán Dijkstra lần lượt cho từng đỉnh, với
cấu trúc dữ liệu Fibonacci-heap hàng đợi ưu tiên nhỏ nhất, độ phức tạp thuật toán để tìm
ĐNN giữa tất cả các cặp đỉnh vào khoảng O(V2LgV+VE). Nếu G có trọng số ở đỉnh âm
nhưng không tạo thành chu trình âm, ta đơn giản tính toán bằng cách tạo mới 1 đỉnh có
trọng số không âm, điều này cho phép chúng ta sử dụng cùng 1 phương pháp. Trọng số
mới W’ của đỉnh phải thoả mãn 2 tính chất quan trọng sau:
1. Với mọi cặp đỉnh u,v thuộc V, 1 đường đi p là ĐNN từ u đến v sử dụng hàm trọng số W
nếu và chỉ nếu p cũng là ĐNN từ u đến v sử dụng hàm trọng số W’.
2. Với mọi cặp đỉnh (u,v), trọng số mới W’(u,v) phải không âm.
Bạn thấy ngay, đồ thị G xác định với hàm trọng số mới W’ có thể thi hành với O(VE).
Giữ nguyên ĐNN bằng REWEIGHTING
Dựa vào các bổ đề, ta có thể dễ dàng chứng minh việc REWEIGHTING thoả mãn tính chất
đầu tiên. Ta sử dụng hàm C để biểu thị trọng số ĐNN bằng hàm trọng số W và C’ để biểu
thị trọng số ĐNN bằng hàm trọng số W’.
Bổ đề 1 - REWEIGHTING không làm thay đổi các đường đi ngắn nhất
Cho 1 ma trận trọng số, đồ thị G = (V,E) với hàm trọng số W: E -> R, hàm H : V->R đối
với bất cứ 1 đỉnh nào đều mang giá trị thực. Với mỗi cặp (u,v) thuộc E, ta định nghĩa

C’(u,v) + H(u) - H(v).
Bây giờ hãy giả sử rằng G và G’ không có chu trình âm. Chúng ta cùng tính H(v) = C(s,v)
cho mọi v thuộc E’. Như vậy, nếu ta tính trọng số mới W’ theo đẳng thức (*), ta có
W’(u,v) = W(u,v) + H(u) - H(v) >= 0 và tính chất thứ 2 đã được thoả mãn. Hình 1(b) thể
hiện đồ thị G’ từ hình 1(a) với cách trọng số cạnh đã được thay đổi.
Tính toán ĐNN giữa mọi cặp đỉnh.
Thuật toán Johnson tìm ĐNN giữa mọi cặp đỉnh sử dụng thuật toán Bellman-Ford và thuật
toán Dijkstra như những chương trình con. Nó bao gồm các đỉnh tích luỹ trong danh sách
kề. Thuật toán thường dùng |V|*|V| ma trận D = d[i,j], tại d[i,j] = C(i,j) hoặc nó báo về đồ
thị nhập vào có chứa chu trình âm. Như các thuật toán tìm ĐNN giữa tất cả các cặp đỉnh
khác, ta có các đỉnh được đánh số từ 1 đến |V|.
CONST fi =’graph.in’;
fo=’graph.out’;
max=100;
VAR H : array[1..max+1] of integer;
W : array[1..max+1,1..max+1] of integer;
Nega_weight : integer;
f,g : text;
PROCEDURE INPUT;
BEGIN
{ mo file ‘graph.in’,’graph.out’, nhap vao ma tran trong so W,so dinh N, bien nega_weight
tinh tong cac canh co trong so < 0 }
END;
PROCEDURE NEW_W;
BEGIN
{tao dinh moi N+1, W[N+1,i]=0 va W[i,N+1]=+ voi i=1..N}
END;
FUNCTION BELLMAN_FORD;{Tim ĐNN tu dinh N+1 den cac dinh khac, luu vao mang
H }
BEGIN

END;
BEGIN
OPEN;
SOLVE;
INPUT_G;
END.