tailieunhanh - GIÁO TRÌNH TOÁN RỜI RẠC - CHƯƠNG V MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ_2

. Thuật toán Floyd: Cho G=(V,E) là một đồ thị có hướng, có trọng số. Để tìm đường đi ngắn nhất giữa mọi cặp đỉnh của G, ta có thể áp dụng thuật toán Dijkstra nhiều lần hoặc áp dụng thuật toán Floyd được trình bày dưới đây. | CHƯƠNG V MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐÒ THỊ . Thuật toán Floyd Cho G V E là một đồ thị có hướng có trọng số. Để tìm đường đi ngắn nhất giữa mọi cặp đỉnh của G ta có thể áp dụng thuật toán Dijkstra nhiều lần hoặc áp dụng thuật toán Floyd được trình bày dưới đây. Giả sử V v1 v2 . vn và có ma trận trọng số là W Wo. Thuật toán Floyd xây dựng dãy các ma trận vuông cấp n là Wk 0 k n như sau procedure Xác định Wn for i 1 to n for j 1 to n W i j m vi Vj W i j là phần tử dòng i cột j của ma trận Wo for k 1 to n if W i k W kj W i j then W ij W i k W kj W i j là phần tử dòng i cột j của ma trận Wk . Định lý Thuật toán Floyd cho ta ma trận W Wn là ma trận khoảng cách nhỏ nhất của đồ thị G. Chứng minh Ta chứng minh bằng quy nạp theo k mệnh đề sau Wk i j là chiều dài đường đi ngắn nhất trong những đường đi nối đỉnh vi với đỉnh Vj đi qua các đỉnh trung gian trong v1 v2 . vk . Trước hết mệnh đề hiển nhiên đúng với k 0. Giả sử mệnh đề đúng với k-1. Xét Wk i j . Có hai trường hợp 1 Trong các đường đi chiều dài ngắn nhất nối vi với vj và đi qua các đỉnh trung gian trong v1 v2 . vk có một đường đi Y sao cho vk Ể Y. Khi đó Y cũng là đường đi ngắn nhất nối vi với vj đi qua các đỉnh trung gian trong v1 v2 . vk-1 nên theo giả thiết quy nạp Wk-i i j chiều dài Y Wk-1 i k Wk-1 k j . Do đó theo định nghĩa của Wk thì Wk i j Wk-1 i j . 2 Mọi đường đi chiều dài ngắn nhất nối vi với vj và đi qua các đỉnh trung gian trong v1 v2 . vk đều chứa vk. Gọi Y vi . vk . vj là một đường đi ngắn nhất như thế thì v1 . vk và vk . vj cũng là những đường đi ngắn nhất đi qua các đỉnh trung gian trong v1 v2 . vk-1 và Wk-1 i k Wk-1 k j chiều dài v1 . vk chiều dài vk . vj chiều dài Y Wk-1 i j . Do đó theo định nghĩa của Wk thì ta có Wk i j Wk-1 i k Wk-1 k j . Thí dụ 2 Xét đồ thị G sau 4 7 2 1 1 4 2 Áp dụng thuật toán Floyd ta tìm được các ô trống là to 7 2 ì 41 W W0 4 3 2 2 . 1 2 í 72 ì 7 11 2 8 ì 41 41 3 3 W1 W2 4 4 8 5 2 9 2 4 2 9 2 4 10 . 1 2 1 15 2