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 DDNN 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 đơngiả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à DDNN từ u đến v sử dụng hàm trọng số W nếu và chỉ nếu p cũng là DDNN 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 DDNN 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ố DDNN bằng hàm trọng số W và C’ để biểu thị trọng số DDNN 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 W’(u,v)=W(u,v) + H(u) – H(v). Với p = {v₀ ,v₁, …, v_k} là đường đi từ đỉnh v⁰ đến đỉnh v_k. Và p là đường đi ngắn nhất từ đỉnh v₀tới đỉnh v_k với hàm trọng số W nếu và chỉ nếu đó cũng là đường đi ngắn nhất với hàm trọng số W’. Đó là, W(p) = C(v₀, v_k) nếu và chỉ nếu W’(p) = C’(v₀, v_k). G có 1 chu trình âm sử dụng hàm trọng số W nếu và chỉ nếu G có 1 chu trình âm sử dụng hàm trọng số W’.

Chứng Minh:

Ta sẽ chứng minhW’(p) = W(p) + H(v₀) – H(vk). (*)

(vì tổng thu gọn H(v₀) - H(v_k) = H(v₀) - H(v₁) + H(v₁)-H(v₂) + … + H(v_k-1) - H(v_k))

Bởi vậy, bất cứ đường đi p nào từ v₀đến v_k đều có W’(p) = W(p) + H(v₀) - H(v_k). Nếu 1 đường đi từ v₀đến v_k là đường đi ngắn nhất trong các đường sử dụng hàm trọng số W, thì nó cũng là DDNN sử dụng W’. Như vậy, W(p) = C(v₀, v_k) nếu và chỉ nếu W’(p) = C’(v₀, v_k).

Cuối cùng, ta thấy rằng G có chu trình âm trên hàm trọng số W nếu và chỉ nếu G có chu trình âm trên hàm trọng số W’. Để ý thấy bất cứ chu trình c={v₀, v₁,… v_k} với v₀ = v_k. Với đẳng thức (*), W’(c) = W(c) + H(v₀) – H(v_k) = W(c), và như vậy c có trọng số âm trên W nếu và chỉ nếu nó có trọng số âm trên W’.

Xây dựng trọng số không âm bằng REWEIGHTING

Vấn đề tiếp theo cần giải quyết là tính chất 2: chúng ta muốn W’(u,v) trở thành không âm cho mọi cặp đỉnh (u,v) thuộc E. Cho 1 ma trận trọng số, đồ thị G=(V,E) với hàm trọng số W: E->R, ta tạo ra 1 đồ thị mới G’=(V’,E’), với V’=V+{s} cho 1 số đỉnh mới s không thuộc V và E’=E+{(s,v):v thuộc V}. Ta khởi tạo hàm trọng số W với W(s,v) = 0 cho mọi đỉnh v thuộc V. (Giải thích: vì s không có cạnh nào vào nó, không thuộc đường đi ngắn nhất nào trong G’). Tuy nhiên, G’ không có chu trình âm nếu và chỉ nếu G không có chu trình âm. Hình minh hoạ dưới đây thể hiện đồ thị G’ tương ứng với đồ thị G của hình 1.

Hình 1. Thuật toán tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh của Johnson chạy trên đồ thị như hình 1(a). Đồ thị G’ với hàm trọng số ban đâu là W. Đỉnh mới có màu đen. Với mọi đỉnh v có H(v) = C(s,v).(b) với mỗi cặp đỉnh (u,v) được sửa trọng số với hàm trọng số W’(u,v) = W(u,v) + H(u) - H(v). ở mỗi đường, đỉnh nguồn u màu đen, và các cạnh mờ là các cây đường đi ngắn nhất được tính toán bởi thuật toán. ở bên trong đỉnh v là các giá trị C’(u,v) và C(u,v) được phân cách bởi 1 đường gạch. Giá trị d[u,v] = C(u,v) là bằng với 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 DDNN giữa mọi cặp đỉnh.

Thuật toán Johnson tìm DDNN 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 DDNN giữa tất cả các cặp đỉnh khác, ta có các đỉnh được đánh số từ 1 đến |V|.

CONSTfi =’graph.in’;

fo=’graph.out’;

max=100;

VARH : array[1..max+1] of integer;

W : array[1..max+1,1..max+1] of integer;

Nega_weight : integer;

f,g : text;

PROCEDUREINPUT;

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 DDNN tu dinh N+1 den cac dinh khac, luu vao mang H }

BEGIN

{Neu do thi co chu trinh am thi ham Bellman_Ford co gia tri false

neu do thi khong chua chu trinh am thi tra ve mang H}

END;

PROCEDURE DIJKSTRA(U:integer);

BEGIN

{ tim DDNN tu dinh U den cac dinh con lai theo thuat toan Dijkstra, gia tri tra ve mang D[u,v] }

END;

PROCEDURE SOLVE;

VAR

BEGIN

NEW_W;

IfBELLMAN_FORD = false

then begin

write(g,’Do thi chua chu trinh am’);

exit;

end;

{ Tinh lai trong so cac canh de luon >= 0}

For u:=1 to N+1 do

Forv:=1 to N+1 do W[u,v]:=W[u,v]+H[u]-H[v];

For u:=1 to N do

Begin

DIJKSTRA(u);

For v:=1 to N do

D[u,v]:=D(u,v)+H[v]-H[u];

End;

END;

PROCEDURE INPUT_G;

BEGIN

{ Ghi ra file ma tran D, dong file }

END;

BEGIN

OPEN;

SOLVE;

INPUT_G;

END.

Trên đây, tôi đã trình bày khá đầy đủ về tư tưởng của thuật toán Johnson, phần cài đặt cũng không khó và sẽ là bài tập dành cho các bạn. Nếu bạn nào gặp khó khăn trong việc cài đặt, có thể gửi email cho tôi theo địa chỉ anhgia137@yahoo.com, tôi sẽ gửi cho bạn chương trình đầy đủ.

School@net (Theo THNT)