Code phần đầu: Thuật toán Floyd Warshall môn Cơ sở dữ liệu | Đại học Văn Lang
Code phần đầu: Thuật toán Floyd Warshall môn Cơ sở dữ liệu | Đại học Văn Lang giúp sinh viên tham khảo, ôn luyện và phục vụ nhu cầu học tập của mình cụ thể là có định hướng, ôn tập, nắm vững kiến thức môn học và làm bài tốt trong những bài kiểm tra, bài tiểu luận, bài tập kết thúc học phần, từ đó học tập tốt và có kết quả cao cũng như có thể vận dụng tốt những kiến thức mình đã học
Preview text:
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