III. THUẬT TOÁN FLOYD WARSHALL
1. Ý tưởng, cách giải 1.1. Ý tưởng:
Từ bài toán đã cho, chuyển các số liệu về dạng ma trận trọng số A. Mỗi ô A[i,j]
được lấp đầy bởi khoảng cách từ đỉnh i tới đỉnh j, nếu không có đường đi nào từ
đỉnh i tới đỉnh j thì ô đó sẽ có giá trị là ∞. Sau bước lặp thứ k, A[i,j] chứa độ dài
đường đi ngắn nhất từ đỉnh i đến đỉnh j (có thể đi qua đỉnh khác rồi đến j), các đỉnh
nó đi qua có chỉ số không vượt quá k. 1.2. Cách giải:
Bước 1: Viết ma trận kề A của đồ thị.
Bước 2: Chọn lần lượt từng đỉnh của đồ thị làm đỉnh trung gian. Giả sử chọn đỉnh
k làm đỉnh trung gian. Ta giữ nguyên hàng k, cột k của ma trận A, giữ nguyên các
phần tử trên đường chéo của A.
Bước 4: Kí hiệu A là ma trận A sau lần lặp thứ k, khi đó A [i,j] được tính theo k k
công thức sau: A [i,j] = min( A [i,j], A [i,k] + A [k,j] ) k k-1 k-1 k-1
Bước 4: Sau đó, ta thực hiện n lần lặp. Sau lần lặp thứ k, ma trận A sẽ chứa độ dài
các đường đi ngắn nhất chỉ đi qua các đỉnh thuộc {1,2,...,k}.
Bước 5: Do đó, sau n lần lặp ta nhận được ma trận A chứa độ dài các đường đi ngắn nhất.
Bảng ý nghĩa các câu lệnh dùng trong khi viết phần mềm Lệnh Cú pháp Ý nghĩa Clear Clear all
-Xóa tất cả các biến, hàm, và các tập tin Input A=input(‘tên biến’) -Nhập vào 1 giá trị cho biến A Min N= Min (A,B)
-Nhập giá trị N bởi giá trị của biến nhỏ hơn trong hai biến A và B Length Length(vecto) -Tính chiều dài vecto Ones Ones(N,N)
-Tạo ra ma trận các phần tử cấp 1 For For -Tạo vòng lặp If- else-end If- (else)-end
-câu lệnh if xác định điều kiện hoặc 1 nhóm điều kiện xảy ra thì cho phép
thực hiện các câu lệnh tiếp theo Fprintf Fprintf( ‘ tên biến ‘)
-Thực hiện ghi định dạng vào màn hình Disp Disp(S) -Trình bày nội dung của biến S ra màn hình