TAILIEUCHUNG - Algorithms Programming - Thuật Toán Số phần 9

Các thuật toán trên đồ thị Từ ma trận trọng số c, thuật toán Floyd tính lại các c[u, v] thành độ dài đường đi ngắn nhất từ u tới v: Với mọi đỉnh k của đồ thị được xét theo thứ tự từ 1 tới n, xét mọi cặp đỉnh u, v. Cực tiểu hoá c[u. | Các thuật toán trên đồ thị 243 nhiều cách làm này rất giống với thuật toán Warshall mà ta đã biết Từ ma trận trọng số c thuật toán Floyd tính lại các c u v thành độ dài đường đi ngắn nhất từ u tới v Với mọi đỉnh k của đồ thị được xét theo thứ tự từ 1 tới n xét mọi cặp đỉnh u v. Cực tiểu hoá c u v theo công thức c u v min c u v c u k c k v Tức là nếu như đường đi từ u tới v đang có lại dài hơn đường đi từ u tới k cộng với đường đi từ k tới v thì ta huỷ bỏ đường đi từ u tới v hiện thời và coi đường đi từ u tới v sẽ là nối của hai đường đi từ u tới k rồi từ k tới v Chú ý rằng ta còn có việc lưu lại vết for k 1 to n do for u 1 to n do for v 1 to n do c u v min c u v c u k c k v Tính đúng của thuật toán Gọi ck u v là độ dài đường đi ngắn nhất từ u tới v mà chỉ đi qua các đỉnh trung gian thuộc tập 1 2 . k . Rõ ràng khi k 0 thì c0 u v c u v đường đi ngắn nhất là đường đi trực tiếp . Giả sử ta đã tính được các ck-1 u v thì ck u v sẽ được xây dựng như sau Nếu đường đi ngắn nhất từ u tới v mà chỉ qua các đỉnh trung gian thuộc tập 1 2 . k lại Không đi qua đỉnh k thì tức là chỉ qua các đỉnh trung gian thuộc tập 1 2 . k - 1 thì ck u v ck-1 u v Có đi qua đỉnh k thì đường đi đó sẽ là nối của một đường đi từ u tới k và một đường đi từ k tới v hai đường đi này chỉ đi qua các đỉnh trung gian thuộc tập 1 2 . k - 1 . k k-1 k-1 c u v c u k c k v . Vì ta muốn ck u v là cực tiểu nên suy ra ck u v min ck-1 u v ck-1 u k ck-1 k v . Và cuối cùng ta quan tâm tới cn u v Độ dài đường đi ngắn nhất từ u tới v mà chỉ đi qua các đỉnh trung gian thuộc tập 1 2 . n . Khi cài đặt thì ta sẽ không có các khái niệm ck u v mà sẽ thao tác trực tiếp trên các trọng số c u v . c u v tại bước tối ưu thứ k sẽ được tính toán để tối ưu qua các giá trị c u v c u k và c k v tại bước thứ k - 1. Tính chính xác của cách cài đặt dưới dạng ba vòng lặp for lồng như trên có thể thấy được do sự tối ưu bắc cầu chỉ làm tăng tốc độ tối ưu các c u v trong mỗi bước Thuật toán Floyd program Shortest_Path_by_Floyd .

• Kỹ thuật lập trình
• Tài liệu IT
• Tài liệu lập trình
• Thuật toán
• Toán logic
• Giải thuật
• Hàm số
• thủ thuật lập trình
• tài chính
• ngân hàng
• kế toán
• quản lý tài chính
• tài liệu tài chính
• tài liệu về ngân hàng
• Tài liệu kinh doanh
• hướng dẫn hạch toán
• Hạch toán doanh nghiệp
• Tài sản doanh nghiệp