Giáo trình hình thành hệ thống ứng dụng nguyên lý điều khiển luồng theo tiến trình biểu diễn số p7

Giả thiết hệ thống mạng không được kiểm soát, nghĩa là tất cả các gói tin đều có thể truy cập tài nguyên của mạng, và bộ đệm tại các nút X, Y và Z có thể được sử dụng bởi bất kỳ gói tin nào. Giả thiết môi trường truyền không có lỗi, lúc này các gói tin không bị sai nhưng vẫn có thể phải được truyền lại nếu nó bị nút mạng hủy do không còn dung lượng bộ đệm để lưu gói tin tạm thời trước khi xử lý. Giả thiết khi gói tin bị mất...
Nội dung trích xuất từ tài liệu:
Giáo trình hình thành hệ thống ứng dụng nguyên lý điều khiển luồng theo tiến trình biểu diễn số p7 Bảng 4.3 Nút init. A(0) B(5) C(1) E(11) D(6) A 0(-) A 0(-) B 0(-) C 0(-) E 0(-) D 0(-) B 5(A) C 5(A) E 4(C) D 4(C) B 4(C) F B  (-) 1(A) 1(A) D 1(A) B 1(A) F 1(A) C  (-) 6(B) 6(B) 6(B) 6(B) D  (-)  (-) 11(B) 11(B) 11(B) 11(B) E  (-)  (-) 13(E) 10(D) F  (-)  (-)  (-)  (-) B(4) F(10) E(10) D(5) F(9) A 0(-) F 0(-) E 0(-) D 0(-) F 0(-) B 4(C) E 4(C) D 4(C) 4(C) 4(C) C 1(A) D 1(A) 1(A) 1(A) 1(A) D 5(B) 5(B) 5(B) 5(B) 5(B) E 10(B) 10(B) 10(B) 10(B) 10(B) F 10(D) 10(D) 10(D) 9(D) 9(D) Thuật toán có thể viết như sau: array[n] while (not(Empty( scan_queue )) i cả các nút khác. Một khả năng có thể đó là sử dụng thuật toán Bellman hoặc thuật toán Dijkstra N lần, bắt đầu từ mỗi nút nguồn. Một khả năng khác, đặc biệt thích hợp với các mạng dày, là sử dụng thuật toán Floyd. Thuật toán Floyd dựa vào quan hệ đệ quy đã được trình bày trong phần giới thiệu thuật toán Dijkstra, nhưng thuật toán này sử dụng quan hệ đệ quy đó theo một cách khác. Lúc này, dij(k) được định nghĩa là đường đi ngắn nhất từ i tới j sử dụng các nút được đánh số là k hoặc thấp hơn như là các nút trung gian. Vì thế dij(0) được định nghiã như là lij, độ dài của liên kết từ nút i tới nút j, nếu liên kết đó tồn tại hoặc dij(0) sẽ bằng vô cùng nếu liên kết đó không tồn tại. Vì vậy, dij(k) = min (dij(k-1), dik(k-1) + dkj(k-1) ) nghĩa là, chúng ta chỉ quan tâm đến việc sử dụng nút k như là một điểm quá giang cho mỗi đường đi từ i tới j. Thuật toán có thể được viết như sau: array[n] Hình 4.7: Ví dụ graph Ví dụ 4.9: Xét graph trong hình 4.7. Mảng chứa khoảng cách ban đầu và mảng chứa nút trung gian cuối cùng của mỗi đường đi được cho trước như sau: Đến Đến A B C D E A B C D E A 0 3 2 - - A A A A A A B - 0 - 2 - B B B B B B T T C - 5 0 - 2 C C C C C C ừ ừ D - - 1 0 1 D D D D D D E - - - - 0 E E E E E E sp_dist pred Chú ý rằng sp_dist có các giá trị 0 trên đường chéo chính và vô cùng lớn (được biểu diễn là dấu -) nếu giữa hai nút không tồn tại một liên kết. Ngoài ra vì graph là graph hữu hướng và không đối xứng nên sp_dist cũng không đối xứng. Xét A ta thấy A là một nút trung gian không ảnh hưởng đến các dãy này vì không có cung nào đi tới nó và vì thế không có đường đi nào đi qua A. Tuy nhiên, xét nút B ta thấy rằng nút B gây nên sự thay đổi ở vị trí (A, D) và (C, D) trong các dãy trên , cụ thể như sau : Đến Đến A B C D E A B C D E T A 0 3 2 5 - T A A A A B A ừ ừ B - 0 - 2 - B B B B B B C - 5 0 7 2 C C C C B C 70 D - - 1 0 1 D D D D D D E - - - - 0 E D D D D D sp_dist pred Tiếp tục xét các nút C, D và E thì gây nên sự thay đổi cụ thể như sau: Đến Đến A B C D E A B C D E A 0 3 2 5 4 A A A A B C B - 0 3 2 3 B B B D B D T T C - 5 0 7 2 C C C C B C ừ ừ D - 6 1 0 1 D D C D D D E - - - - 0 E E E E E E sp_dist pred Các thuật toán tìm đi ngắn nhất mở rộng Trong quá trình thiết kế v à phân tích mạng đôi khi chúng ta phải tìm đường đi ngắn nhất giữa mọi cặp các nút (hoặc một số cặp) sau khi có sự thay đổi độ dài một cung. Việc thay đổi này bao gồm cả việc thêm hoặc loại bỏ một cung (trong trường hợp đó độ dài của cung có thể được xe ...