tailieunhanh - GIÁO TRÌNH LÝ THUYẾT ĐỒ THỊ - CHƯƠNG 6

BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT Trong các ứng dụng thực tế, vài toán tìm đường đi ngắn nhất giữa hai đỉnh của một đồ thị liên thông có một ý nghĩa to lớn. Có thể dẫn về bài toán như vậy nhiều bài toán thực tế quan trọng. Ví dụ, bài toán chọn một hành trình tiết kiệm nhất (theo tiêu chuẩn hoặc khoảng cách hoặc thời gian hoặc chi phí) trên một mạng giao thông đường bộ, đường thủy hoặc đường không; bài toán chọn một phương pháp tiết kiệm nhất để đưa ra một hệ thống động. | CHƯƠNG 6 BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT Trong các ứng dụng thực tế vài toán tìm đường đi ngắn nhất giữa hai đỉnh của một đồ thị liên thông có một ý nghĩa to lớn. Có thể dẫn về bài toán như vậy nhiều bài toán thực tế quan trọng. Ví dụ bài toán chọn một hành trình tiết kiệm nhất theo tiêu chuẩn hoặc khoảng cách hoặc thời gian hoặc chi phí trên một mạng giao thông đường bộ đường thủy hoặc đường không bài toán chọn một phương pháp tiết kiệm nhất để đưa ra một hệ thống động lực từ trạng thái xuất phát đến trạng một trạng thái đích bài toán lập lịch thi công các công các công đoạn trong một công trình thi công lớn bài toán lựa chọn đường truyền tin với chi phí nhỏ nhất trong mạng thông tin . Hiện nay có rất nhiều phương pháp để giải các bài toán như vậy. Thế nhưng thông thường các thuật toán được xây dựng dựa trên cơ sở lý thuyết đồ thị tỏ ra là các thuật toán có hiệu quả cao nhất. Trong chương này chúng ta sẽ xét một số thuật toán như vậy. 1. CÁC KHÁI NIỆM MỞ ĐẦU Trong chương này chúng ta chỉ xét đồ thị có hướng G V E V n E m với các cung được gán trọng số nghĩa là mỗi cung u v I E của nó được đặt tương ứng với một số thực a u v gọi là trọng số của nó. Chúng ta sẽ đặt a u v nếu u v I E. Nếu dãy Vo V1 . . . Vp là một đường đi trên G thì độ dài của nó được định nghĩa là tổng sau p ảa vi-i Vi . i 1 tức là độ dài của đường đi chính là tổng của các trọng số trên các cung của nó. Chú ý rằng nếu chúng ta gán trọng số cho tất cả cung đều bằng 1 thì ta thu được định nghĩa độ dài của đường đi như là số cung của đường đi giống như trong các chương trước đã xét . Bài toán tìm đường đi ngắn nhất trên đồ thị dưới dạng tổng quát có thể phát biểu như sau tìm đường đi có độ dài nhỏ nhất từ một đỉnh xuất phát s I V đến đỉnh cuối đích t I V. Đường đi như vậy ta sẽ gọi là đường đi ngắn nhất từ s đến t còn độ dài của nó ta sẽ ký hiệu là d s t và còn gọi là khoảng cách từ s đến t khoảng cách định nghĩa như vậy có thể là số âm . Nếu như không tồn tại đường đi từ s đến t thì ta sẽ đặt d s t .