Giáo trình hình thành công cụ phân tích hàm mũ với tham số theo tiến trình Poisson với tham số p7

Tham khảo tài liệu giáo trình hình thành công cụ phân tích hàm mũ với tham số theo tiến trình poisson với tham số p7, khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Giáo trình hình thành công cụ phân tích hàm mũ với tham số theo tiến trình Poisson với tham số p7Bả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ánBellman hoặc thuật toán Dijkstra N lần, bắt đầu từ mỗi nút nguồn. Mộtkhả năng khác, đặc biệt thích hợp với các mạng dày, là sử dụng thuậttoán Floyd. Thuật toán Floyd dựa vào quan hệ đệ quy đã được trình bày trongphần giới thiệu thuật toán Dijkstra, nhưng thuật toán này sử dụng quanhệ đệ 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ặcthấ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ếtnhư sau: array[n] Hình 4.7: Ví dụ graphVí dụ 4.9: Xét graph trong hình 4.7. Mảng chứa khoảng cách ban đầu và mảngchứ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 BT 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 predChú ý 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ộtliên kết. Ngoài ra vì graph là graph hữu hướng và không đối xứng nênsp_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ãynày vì không có cung nào đi tới nó và vì thế không có đường đi nào điqua 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 ET 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 predCá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 xem ...