CÁC PHẦN TỬ CỦA MA TRẬN T CÓ THỂ RẤT LỚN, HƠN NỮA CHÚNG TA CHỈ QUAN TÂM ĐẾN TÍNHCHẤT KHÁC 0 CỦA CÁC PHẦN TỬ, NÊN CÓ THỂ XEM MA TRẬN KỀ A NHƯ MA TRẬN LOGIC VÀTRONG PHÉP NHÂN MA TRẬN TA THAY CÁC PHÉP TOÁN SỐ HỌC + , * BẰNG CÁC PHÉP TOÁNLOGIC OR VÀ AND

2. Các phần tử của ma trận T có thể rất lớn, hơn nữa chúng ta chỉ quan tâm đến tính

chất khác 0 của các phần tử, nên có thể xem ma trận kề A như ma trận logic và

trong phép nhân ma trận ta thay các phép toán số học + , * bằng các phép toán

logic OR và AND. Khi đó, ta dùng thuật toán Warshall sau đây để tính ma trận bao

đóng bắc cầu logic AS. Các phần tử logic của ma trận AS cho biết có hay không

đường đi giữa tất cả các cặp đỉnh của đồ thị đã cho.

Thuật toán 1.4 (Warshall):

Dữ liệu: Ma trận kề logic A của đồ thị G.

Kết quả: Ma trận bao đóng bắc cầu logic AS.

1 Begin

2 for i := 1 to n do

3 for j := 1 to n do AS[i,j] := A[i,j] ;

4 for k := 1 to n-1 do

5 for i := 1 to n do

6 for j := 1 to n do

7 if ! AS[i,j] then AS[i,j] := AS[i,k] and AS[k,j]

8 End .

Hiển nhiên, thuật toán có độ phức tạp là O(n ).